3720. Lexicographically Smallest Permutation Greater Than Target

Problem Overview

You need the lexicographically smallest permutation of s that beats target.

Intuition

You need the lexicographically smallest permutation of s that beats target. Among all valid answers, the best one shares the longest possible prefix with target, then places the smallest letter still available that is greater than target at the first difference, then fills the rest with the leftover letters in ascending order. Recording every feasible step-up while walking left to right and keeping the rightmost one yields that answer.

Algorithm

1Count the 26 letter frequencies in s.
2For i from 0 to n-1: if any remaining letter is > target[i], remember i and the smallest such letter. Then try to spend one copy of target[i]; if none remains, stop.
3If no step-up was ever possible, return "".
4Rebuild counts from s. Copy target[0..bestPos-1], place bestChar, then append remaining letters from a to z.

Example Walkthrough

Input: s = "abc", target = "bba"

1.At index 0, c > b is possible. Match b and continue.
2.At index 1, c > b is possible (rightmost step-up). Cannot match a second b, so stop.
3.Rebuild: prefix "b", place c, leftover a -> "bca".

Output: "bca"

Common Pitfalls

•A later first difference is lexicographically smaller than an earlier one when both beat target, so keep the rightmost feasible step-up.
•Check for a larger letter before consuming target[i] for the matched prefix.
•If s and target use the same multiset and target is already the largest permutation, the answer is "".
•After the step-up, sort the suffix ascending, not descending.

3720.cs

// Approach: Count letters in s. Walk left to right: at each index, record
// the smallest letter still available that is > target[i] (a valid first
// difference). Then try to match target[i] and continue. The rightmost such
// difference gives the lexicographically smallest answer; rebuild by copying
// the matched prefix, placing that letter, and appending the rest sorted.
// Complexity: O(n) time (alphabet size 26) and O(1) extra space besides the
// output string.
public class Solution
{
    public string LexGreaterPermutation(string s, string target)
    {
        int[] count = new int[26];
        foreach (char c in s)
            count[c - 'a']++;

        int n = s.Length;
        int bestPos = -1;
        char bestChar = '\0';

        for (int i = 0; i < n; i++)
        {
            int t = target[i] - 'a';
            for (int c = t + 1; c < 26; c++)
            {
                if (count[c] > 0)
                {
                    bestPos = i;
                    bestChar = (char)('a' + c);
                    break;
                }
            }

            if (count[t] == 0)
                break;
            count[t]--;
        }

        if (bestPos < 0)
            return "";

        Array.Fill(count, 0);
        foreach (char c in s)
            count[c - 'a']++;

        char[] ans = new char[n];
        for (int i = 0; i < bestPos; i++)
        {
            ans[i] = target[i];
            count[target[i] - 'a']--;
        }

        ans[bestPos] = bestChar;
        count[bestChar - 'a']--;

        int idx = bestPos + 1;
        for (int c = 0; c < 26; c++)
        {
            while (count[c]-- > 0)
                ans[idx++] = (char)('a' + c);
        }

        return new string(ans);
    }
}

Was this solution helpful?