3517. Smallest Palindromic Rearrangement I

Description

You are given a string s.

Return the palindromic 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 <= 105
• s consists of lowercase English letters.
• s is guaranteed to be palindromic.

 

Solutions

Solution: Counting Sort

• Time complexity: O(26+n)
• Space complexity: O(26 -> 1)

 

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
const smallestPalindrome = function (s) {
  const BASE_CODE = 'a'.charCodeAt(0);
  const counts = Array.from({ length: 26 }, () => 0);
  let prefix = '';
  let suffix = '';
  let middle = '';

  for (const char of s) {
    const code = char.charCodeAt(0) - BASE_CODE;

    counts[code] += 1;
  }

  for (let code = 0; code < 26; code++) {
    const count = counts[code];

    if (!count) continue;

    const char = String.fromCharCode(code + BASE_CODE);
    const half = Math.floor(count / 2);
    const target = char.repeat(half);

    if (count % 2) {
      middle = char;
    }

    prefix += target;
    suffix = `${target}${suffix}`;
  }

  return `${prefix}${middle}${suffix}`;
};