Is Smallest Palindromic Rearrangement I easy or hard?

The problem is typically rated Medium. The challenge is recognizing the palindrome frequency constraint and ensuring the final result is the smallest lexicographically. Once you apply a counting strategy, the implementation becomes straightforward.

Smallest Palindromic Rearrangement I Python/Java solution

Most implementations follow the same logic across languages: count character frequencies, construct the left half using freq[c] // 2 copies, optionally add a middle character with odd frequency, and mirror the left side. The FleetCode solution provides implementations in Python, Java, C++, Go, and TypeScript.

How to solve Smallest Palindromic Rearrangement I in O(n)?

Use a counting approach. First compute the frequency of each character, verify that at most one character has an odd count, then append freq[c] / 2 characters to the left half in alphabetical order. Place the odd character in the middle if it exists and append the reverse of the left half to complete the palindrome.

What is the best approach for Smallest Palindromic Rearrangement I?

The best approach uses frequency counting. Count how many times each character appears, ensure at most one character has an odd frequency, then build half the palindrome in lexicographic order and mirror it. This method runs in O(n + k) time where k is the alphabet size and guarantees the smallest lexicographic palindrome.

Is Smallest Palindromic Rearrangement I asked at Google/Amazon/Meta?

Palindrome construction and character frequency problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving palindrome permutations, rearrangements, and lexicographic constraints are common string interview questions.

What data structure is used in Smallest Palindromic Rearrangement I?

A frequency array or hash map is the main data structure. It stores how many times each character appears, enabling a counting-sort style traversal to build the lexicographically smallest palindrome efficiently.

What is the time complexity of Smallest Palindromic Rearrangement I?

The optimal solution runs in O(n + k) time using a counting frequency array, where n is the length of the string and k is the character set size. Building the palindrome requires iterating through the frequency counts and constructing two halves of the result string.

Description Hints 2 Solution Video 13:07

3517. Smallest Palindromic Rearrangement I

Medium74.5% acceptance3 companies

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 <= 10⁵
s consists of lowercase English letters.
s is guaranteed to be palindromic.

Asked at 3 companies

Google Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Consider a palindrome as composed of two mirror-image halves.

Hint 2

Construct one half (using s), and then the other half is its reverse to obtain the lexicographically smallest permutation.

13:07

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

3517. Smallest Palindromic Rearrangement I

Asked at 3 companies

Topics

Hints open one at a time

Similar problems