Smallest Palindromic Rearrangement I

Smallest Palindromic Rearrangement I

What is this problem about?

The "Smallest Palindromic Rearrangement I" interview question asks you to take a string and determine if its characters can be rearranged into a palindrome. If they can, you need to find the lexicographically smallest such palindrome. A palindrome reads the same forwards and backwards. This "Smallest Palindromic Rearrangement I coding problem" combines frequency counting with lexicographical optimization.

Why is this asked in interviews?

Microsoft and Amazon ask this to test your understanding of palindromic properties and string construction. It requires you to know that for a palindrome to exist, at most one character can have an odd frequency. It also evaluates your ability to build a string by placing the smallest available characters at the "edges" (start and end) and working your way inward.

Algorithmic pattern used

This follows the "Sorting, Counting Sort, and String interview pattern".

1. Count the frequency of each character in the input string.
2. Verify the palindrome condition: No more than one character has an odd count.
3. To build the lexicographically smallest palindrome:
   • Take half of the occurrences of each character (in alphabetical order) and append them to the "left half" of the result.
   • If there is a character with an odd count, it will be the "middle" character.
   • The "right half" is simply the reverse of the left half.
   • Final string = left_half + middle + right_half.

Example explanation

String: aabbcc

1. Frequencies: a:2, b:2, c:2. All even. OK.
2. Build left half: Take one 'a', one 'b', one 'c'. left = "abc".
3. Middle: None.
4. Right half: reverse("abc") = "cba". Result: "abccba". String: aabbc
5. Frequencies: a:2, b:2, c:1. One odd ('c'). OK.
6. Build left: "ab". Middle: "c". Right: "ba". Result: "abcba".

Common mistakes candidates make

The most frequent mistake is not using alphabetical order when building the left half, which fails the "lexicographically smallest" requirement. Another error is incorrectly handling the odd-frequency character or failing to realize that a palindrome cannot be formed if multiple characters have odd frequencies. Some candidates also forget to handle the reverse part of the string construction efficiently.

Interview preparation tip

Always use a frequency array or a sorted map when lexicographical order is required. This ensures that you process characters in the correct order (a, b, c...) without extra sorting steps. This technique is a staple for many "Smallest Palindromic Rearrangement I interview question" variants.