3518. Smallest Palindromic Rearrangement II

Hash Table String Math combinatorics Counting

Problem Overview

Same as part I: a palindrome is fixed by its left half plus an optional middle.

Intuition

Same as part I: a palindrome is fixed by its left half plus an optional middle. Here we need the k-th distinct left-half multiset permutation in lex order (1-indexed), then mirror it. Instead of generating all permutations, at each position try letters from a to z and use combination counts to skip whole blocks when they are smaller than the remaining k.

Algorithm

1Count character frequencies. If more than one odd count exists, return "" (not needed when s is already a palindrome).
2For each letter, put freq/2 into halfCount; keep the odd letter as midLetter.
3If k exceeds the number of distinct multiset permutations of halfCount (capped at MAX), return "".
4Build the left half position by position: for each letter with remaining count, temporarily use one and compute arrangements of the rest.
5If arrangements >= k, keep that letter; else subtract arrangements from k, restore the count, and try the next letter.
6Return leftHalf + midLetter + reverse(leftHalf).

Example Walkthrough

Input: s = "abba", k = 2

1.halfCount has one a and one b; mid is empty. Distinct left halves: "ab", "ba".
2.Total permutations = 2.
3.For k = 2: first position skips "a..." (1 arrangement) and takes "b", then "a" -> left = "ba".
4.Answer = "baab".

Output: "baab"

Common Pitfalls

•k is 1-indexed among distinct palindromes, not 0-indexed.
•Combination counts can overflow int; use long and cap at MAX because k <= 1e6.
•List.Reverse() mutates in place and returns void - copy to an array before reversing for the right half.
•Restore halfCount[i] when skipping a letter; otherwise later positions use wrong frequencies.
•Return "" when k is larger than the number of distinct palindromic permutations.

3518.cs

public class Solution
{
    // Approach: Only the left half of a palindrome can vary. Take half of each
    // character count (and the odd middle letter). Cap combination counts at
    // MAX (> max k). For each left position, try letters a..z: tentatively use
    // one, count remaining multiset permutations; if that block is >= k, keep
    // the letter, else subtract and try the next. Mirror the left half for the answer.
    // Complexity: O(26 * n * 26) time for building the half with combination math,
    // O(1) extra beyond the half (26 letters).
    private readonly int MAX = 1000001;

    public string SmallestPalindrome(string s, int k)
    {
        var count = new Dictionary<char, int>();
        foreach (var c in s)
        {
            if (!count.ContainsKey(c))
                count[c] = 0;
            count[c]++;
        }

        if (!IsPalindromePossible(count))
            return "";

        var (halfCount, midLetter) = GetHalfCountAndMidLetter(count);
        var totalPerm = CalculateTotalPermutations(halfCount);
        if (k > totalPerm)
            return "";

        var leftHalf = GenerateLeftHalf(halfCount, k);
        char[] rightChars = leftHalf.ToArray();
        Array.Reverse(rightChars);
        return new string(leftHalf.ToArray()) + midLetter + new string(rightChars);
    }

    private bool IsPalindromePossible(Dictionary<char, int> count)
    {
        int oddCount = count.Values.Count(freq => freq % 2 == 1);
        return oddCount <= 1;
    }

    private (List<int>, string) GetHalfCountAndMidLetter(Dictionary<char, int> count)
    {
        var halfCount = new List<int>(new int[26]);
        string midLetter = "";
        foreach (var kvp in count)
        {
            int idx = kvp.Key - 'a';
            halfCount[idx] = kvp.Value / 2;
            if (kvp.Value % 2 == 1)
                midLetter = kvp.Key.ToString();
        }
        return (halfCount, midLetter);
    }

    private int CalculateTotalPermutations(List<int> halfCount)
    {
        return CountArrangements(halfCount);
    }

    private List<char> GenerateLeftHalf(List<int> halfCount, int k)
    {
        int halfLen = halfCount.Sum();
        var left = new List<char>();
        for (int _ = 0; _ < halfLen; _++)
        {
            for (int i = 0; i < halfCount.Count; i++)
            {
                if (halfCount[i] == 0)
                    continue;

                halfCount[i]--;
                int arrangements = CountArrangements(halfCount);
                if (arrangements >= k)
                {
                    left.Add((char)(i + 'a'));
                    break;
                }
                else
                {
                    k -= arrangements;
                    halfCount[i]++;
                }
            }
        }
        return left;
    }

    private int CountArrangements(List<int> count)
    {
        int total = count.Sum();
        long res = 1;
        foreach (var freq in count)
        {
            res *= NChooseK(total, freq);
            if (res >= MAX)
                return MAX;
            total -= freq;
        }
        return (int)res;
    }

    private int NChooseK(int n, int k)
    {
        if (k > n)
            return 0;
        if (k > n - k)
            k = n - k;
        long res = 1;
        for (int i = 1; i <= k; i++)
        {
            res = res * (n - i + 1) / i;
            if (res >= MAX)
                return MAX;
        }
        return (int)res;
    }
}

Was this solution helpful?