3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

Problem Overview

A palindrome is determined by its left half (and the middle letter when n is odd).

Intuition

A palindrome is determined by its left half (and the middle letter when n is odd). You need the smallest palindromic rearrangement of s that is strictly greater than target. Match target from the left while you still can, but a match at one index does not force the smallest fill to win later. If target[i] still fits, recurse; otherwise place the smallest letter > target[i], fill the rest with the smallest available letters, and mirror to finish.

Algorithm

1Count letters in s. If more than one odd count, no palindrome exists.
2DFS/build from left to right on the half (plus middle). When still tied to target, try target[i] and recurse.
3If target[i] cannot be extended to any beating palindrome, try the next letter.
4When you place c > target[i], fill the remaining half with the smallest letters, set the middle if needed, mirror, and return.
5At the end, return the built string only if it is strictly greater than target.

Example Walkthrough

Input: s = "aabb", target = "abaa"

1.Palindromes are "abba" and "baab". Both beat "abaa".
2.Match target through index 6 is not needed here: match "abababa" on the left half, then bump index 7 from a to b.
3.Smallest fill after that bump gives "abba".

Output: "abba"

Common Pitfalls

•Do not require target[i] == target[n-1-i] when matching a pair. Only the left choice is fixed; the right mirrors it.
•Checking only the smallest completion after a match is wrong. A later index may still provide the needed bump.
•Rightmost-bump logic from ordinary permutations (LC 3720) is not correct for palindromes.
•If every position matches and the full palindrome equals target, return "".

3734.cs

// Approach: A palindrome is fixed by its left half (and middle if n is odd).
// Build left to right. While still matching target, try target[i] and recurse;
// a later position may still beat target even if the smallest fill does not.
// Otherwise pick the smallest letter > target[i], fill the rest with smallest
// letters, and return.
// Complexity: O(26 * n) per backtrack level in practice, O(n) extra space.
public class Solution
{
    public string LexPalindromicPermutation(string s, string target)
    {
        int n = s.Length;
        int half = n / 2;
        bool odd = n % 2 == 1;
        int steps = half + (odd ? 1 : 0);
        int[] cnt = new int[26];
        int odds = 0;

        foreach (char c in s)
        {
            if ((++cnt[c - 'a'] & 1) == 1)
                odds++;
            else
                odds--;
        }

        if (odds > 1)
            return "";

        char[] left = new char[half];
        char mid = '\0';
        return Build(0, true, left, ref mid, cnt, target, half, odd, n, steps) ?? "";
    }

    private static string Build(
        int pos,
        bool tight,
        char[] left,
        ref char mid,
        int[] cnt,
        string target,
        int half,
        bool odd,
        int n,
        int steps)
    {
        if (pos == steps)
        {
            string ans = ToString(left, mid, n, half, odd);
            return string.CompareOrdinal(ans, target) > 0 ? ans : null;
        }

        bool isMiddle = odd && pos == half;
        int lo = tight ? target[pos] - 'a' : 0;

        for (int c = lo; c < 26; c++)
        {
            if (!CanTake(cnt, c, isMiddle))
                continue;

            Take(cnt, c, isMiddle);
            char savedMid = mid;

            if (isMiddle)
                mid = (char)('a' + c);
            else
                left[pos] = (char)('a' + c);

            if (tight && c == target[pos] - 'a')
            {
                string ans = Build(pos + 1, true, left, ref mid, cnt, target, half, odd, n, steps);
                if (ans != null)
                    return ans;
            }
            else
            {
                FillSmallest(left, ref mid, isMiddle ? half : pos + 1, cnt, odd, half);
                string ans = ToString(left, mid, n, half, odd);
                if (string.CompareOrdinal(ans, target) > 0)
                    return ans;
            }

            Untake(cnt, c, isMiddle);
            mid = savedMid;
        }

        return null;
    }

    private static bool CanTake(int[] cnt, int c, bool isMiddle)
    {
        return isMiddle ? cnt[c] > 0 : cnt[c] >= 2;
    }

    private static void Take(int[] cnt, int c, bool isMiddle)
    {
        cnt[c] -= isMiddle ? 1 : 2;
    }

    private static void Untake(int[] cnt, int c, bool isMiddle)
    {
        cnt[c] += isMiddle ? 1 : 2;
    }

    private static void FillSmallest(char[] left, ref char mid, int from, int[] cnt, bool odd, int half)
    {
        for (int j = from; j < half; j++)
        {
            for (int c = 0; c < 26; c++)
            {
                if (cnt[c] >= 2)
                {
                    left[j] = (char)('a' + c);
                    cnt[c] -= 2;
                    break;
                }
            }
        }

        if (odd && mid == '\0')
        {
            for (int c = 0; c < 26; c++)
            {
                if (cnt[c] > 0)
                {
                    mid = (char)('a' + c);
                    cnt[c]--;
                    break;
                }
            }
        }
    }

    private static string ToString(char[] left, char mid, int n, int half, bool odd)
    {
        char[] ans = new char[n];
        for (int i = 0; i < half; i++)
        {
            ans[i] = left[i];
            ans[n - 1 - i] = left[i];
        }

        if (odd)
            ans[half] = mid;

        return new string(ans);
    }
}

Was this solution helpful?