Description
You are given a palindromic string s.
Return the lexicographically smallest palindromic permutation of s.
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 <= 105sconsists of lowercase English letters.sis guaranteed to be palindromic.
Solutions
This is a leaner variant of the same idea that only inspects the first half of the string (halfLen = floor(s.length / 2)), counting the frequency of each letter that appears there; it then walks the alphabet from a to z, appending each letter (repeated by its count) to left and prepending the same run to right so the two halves become mirror images of each other, and finally stitches the result together as left + (middle character, taken as-is from s if the length is odd) + right — effectively sorting just the first half alphabetically and mirroring it to produce the smallest palindrome, while leaving the original middle character untouched.
/**
* @param {string} s
* @return {string}
*/
var smallestPalindrome = function(s) {
const freq = Array(26).fill(0);
const halfLen = Math.floor(s.length / 2);
for (let i = 0; i < halfLen; i++) {
freq[s.charCodeAt(i) - 97]++;
}
let left = '';
let right = '';
for (let i = 0; i < 26; i++) {
if (freq[i] === 0) {
continue;
}
const char = String.fromCharCode(97 + i);
const chars = char.repeat(Math.floor(freq[i]));
left = left + chars;
right = chars + right;
}
return left + (s.length & 1 ? s[halfLen] : '') + right;
};