DDSA Solutions

3517. Smallest Palindromic Rearrangement I

MediumView on LeetCode
StringSortingCountingGreedy

Problem Overview

s is guaranteed to be a palindrome, so rearranging it into another palindrome only means reordering the left half (and optionally the middle).

Intuition

s is guaranteed to be a palindrome, so rearranging it into another palindrome only means reordering the left half (and optionally the middle). The lexicographically smallest palindrome is the one whose left half is the sorted multiset of characters from that half, mirrored on the right.

Algorithm

  1. 1Take the first n/2 characters of s as the left half.
  2. 2Sort that half ascending.
  3. 3If n is odd, keep s[n/2] as the middle character; otherwise the middle is empty.
  4. 4Return sortedHalf + middle + reverse(sortedHalf).

Example Walkthrough

Input: s = "babab"

  1. 1.Left half = "ba"; middle = "b".
  2. 2.Sort left half -> "ab".
  3. 3.Mirror: "ab" + "b" + "ba" = "abbba".

Output: "abbba"

Common Pitfalls

  • •Do not sort the whole string - that can break the palindrome pairing.
  • •The middle character (odd length) must stay in the center; only the halves are rearranged.
  • •Because s is already a palindrome, counting frequencies is optional - sorting the existing left half is enough.
  • •A counting pass over a..z would make this O(n) instead of O(n log n) if needed.
3517.cs
C#
public class Solution
{
    // Approach: s is already a palindrome, so the left half (and optional middle)
    // fully determines the character multiset. Sort that left half ascending,
    // keep the middle character when n is odd, and append the reverse of the
    // sorted half to form the lexicographically smallest palindromic permutation.
    // Complexity: O(n log n) time and O(n) space.
    public string SmallestPalindrome(string s)
    {
        int n = s.Length;
        string sortedHalf = GetSortedHalf(s);
        return sortedHalf + (n % 2 == 1 ? s[n / 2].ToString() : "") + Reversed(sortedHalf);
    }

    private string GetSortedHalf(string s)
    {
        string half = s.Substring(0, s.Length / 2);
        char[] chars = half.ToCharArray();
        Array.Sort(chars);
        return new string(chars);
    }

    private string Reversed(string s)
    {
        var sb = new StringBuilder(s);
        for (int i = 0, j = s.Length - 1; i < j; i++, j--)
        {
            char temp = sb[i];
            sb[i] = sb[j];
            sb[j] = temp;
        }
        return sb.ToString();
    }
}
Was this solution helpful?

Related Problems