Problem

You are given a palindromic string s. published: true Return the lexicographically smallest palindromic permutation of s.

Examples

Example 1

1
2
3
4
5

Input: s = "z"
Output: "z"
Explanation:
A string of only one character is already the lexicographically smallest
palindrome.

Example 2

1
2
3
4
5

Input: s = "babab"
Output: "abbba"
Explanation:
Rearranging `"babab"` -> `"abbba"` gives the smallest lexicographic
palindrome.

Example 3

1
2
3
4
5

Input: s = "daccad"
Output: "acddca"
Explanation:
Rearranging `"daccad"` -> `"acddca"` gives the smallest lexicographic
palindrome.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.
  • s is guaranteed to be palindromic.

Method 1 – Greedy Character Placement

Intuition

To get the lexicographically smallest palindromic permutation, place the smallest available characters at the start and end, and the next smallest, and so on. If the length is odd, the center is the remaining odd-count character.

Approach

  1. Count the frequency of each character in s.
  2. For each character in lex order, place half its count at the start and half at the end (mirrored).
  3. If there is a character with an odd count, place it in the center.
  4. Return the constructed palindrome.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string smallestPalindrome(string s) {
        vector<int> cnt(26);
        for (char c : s) cnt[c-'a']++;
        string left = "", mid = "";
        for (int i = 0; i < 26; ++i) {
            if (cnt[i] % 2) mid += (char)('a'+i);
            left += string(cnt[i]/2, 'a'+i);
        }
        string right = left; reverse(right.begin(), right.end());
        return left + mid + right;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public String smallestPalindrome(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c-'a']++;
        StringBuilder left = new StringBuilder(), mid = new StringBuilder();
        for (int i = 0; i < 26; ++i) {
            if (cnt[i] % 2 == 1) mid.append((char)('a'+i));
            for (int j = 0; j < cnt[i]/2; ++j) left.append((char)('a'+i));
        }
        String right = left.reverse().toString();
        left.reverse();
        return left.toString() + mid.toString() + right;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        from collections import Counter
        cnt = Counter(s)
        left, mid = [], ''
        for ch in sorted(cnt):
            if cnt[ch] % 2:
                mid = ch
            left.append(ch * (cnt[ch]//2))
        return ''.join(left) + mid + ''.join(left)[::-1]

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. Each character is processed a constant number of times.
  • 🧺 Space complexity: O(n), for the output string and counters.

Solution

Method 1 -

Code

Complexity

  • ⏰ Time complexity: O(nnnxxxnnn)
  • 🧺 Space complexity: O(nnnxxx)