fault"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:Tdb1,

Problem

You are given a palindromic string s.

Return the lexicographically smallest palindromic permutation of s.

Examples

Example 1

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

Example 2

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

Example 3

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

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

Code

[{"language":"C++","code":"#include <string>\n#include <vector>\nusing namespace std;\nclass Solution {\npublic:\n    string smallestPalindrome(string s) {\n        vector<int> cnt(26);\n        for (char c : s) cnt[c-'a']++;\n        string left = \"\", mid = \"\";\n        for (int i = 0; i < 26; ++i) {\n            if (cnt[i] % 2) mid += (char)('a'+i);\n            left += string(cnt[i]/2, 'a'+i);\n        }\n        string right = left; reverse(right.begin(), right.end());\n        return left + mid + right;\n    }\n};","lang":"cpp"},{"language":"Java","code":"class Solution {\n    public String smallestPalindrome(String s) {\n        int[] cnt = new int[26];\n        for (char c : s.toCharArray()) cnt[c-'a']++;\n        StringBuilder left = new StringBuilder(), mid = new StringBuilder();\n        for (int i = 0; i < 26; ++i) {\n            if (cnt[i] % 2 == 1) mid.append((char)('a'+i));\n            for (int j = 0; j < cnt[i]/2; ++j) left.append((char)('a'+i));\n        }\n        String right = left.reverse().toString();\n        left.reverse();\n        return left.toString() + mid.toString() + right;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def smallestPalindrome(self, s: str) -> str:\n        from collections import Counter\n        cnt = Counter(s)\n        left, mid = [], ''\n        for ch in sorted(cnt):\n            if cnt[ch] % 2:\n                mid = ch\n            left.append(ch * (cnt[ch]//2))\n        return ''.join(left) + mid + ''.join(left)[::-1]","lang":"python"}]

Complexity

⏰ Time complexity: O(n), where n is the length of s. Each character is proce

Related Tags

Continue Practicing