410. Lexicographically Smallest Permutation Greater Than Target

Reuse target's prefix for as long as the available letters allow, then at the last position we can, place the smallest letter strictly greater than target's letter there and dump the rest in ascending order — the smallest possible tail.

Idea

We want the smallest permutation of s that is strictly greater than target. Any string strictly greater than target must share some (possibly empty) prefix with target and then, at the first differing position p, use a letter strictly greater than target[p]. To keep the whole string as small as possible we want that break position p as far right as possible, and after it we should place the smallest legal letter and then the smallest possible tail (all remaining letters in ascending order).

So the plan is:

1. Match target from the left for as long as the letters of s allow.
2. At the deepest position we can, place the smallest available letter > target[p].
3. Fill everything after with the remaining letters sorted ascending.
4. If no letter > target[p] is available at p, backtrack: give back the letter we matched at p-1 and try to break there instead.

Because every letter is available in bounded supply, we track a frequency count of s rather than the letters themselves.

Algorithm

1. Build cnt, the frequency of each letter in s.
2. Greedy match: walk i from 0; while cnt[target[i]] > 0, consume it (cnt[target[i]] -= 1) and record it in prefix. Stop at the first position whose letter isn't available (or at the end).
3. Let p be that stopping index. Now try to break at p, then p-1, p-2, ... :
   • If p < n, scan letters c from target[p] + 1 up to 'z'; the first with cnt[c] > 0 is our break. Place it, then append every remaining letter (by cnt) in ascending order. Return prefix[:p] + c + tail.
   • Otherwise decrement p, and restore the letter matched at the new p (cnt[target[p]] += 1) so it's available to break with.
4. If p falls below 0, no answer exists — return "".

When we reach the end of target with a full match (p == n), the built string equals target, which is not strictly greater — the backtracking loop handles this by immediately stepping p back into range.

Worked example: s = "abc", target = "bba"

cnt = {a:1, b:1, c:1}.

1. Match: target[0]='b', available → consume, prefix="b", cnt={a:1,b:0,c:1}. target[1]='b', cnt['b']=0 → stop. p = 1.
2. Break at p=1: target[1]='b'; smallest available letter > 'b' is 'c'. Place it: cnt={a:1,b:0,c:0}.
3. Tail (ascending): remaining is one 'a' → "a".
4. Answer: prefix[:1] + 'c' + 'a' = "bca".

Check: permutations of "abc" in order are abc, acb, bac, bca, cab, cba; the smallest strictly greater than "bba" is indeed "bca".

Why backtracking is needed: s = "baba", target = "bbaa"

We match b, b, a, a fully (p = 4), but that equals target — not greater. Stepping back to p = 3, 2, 1, 0 and restoring counts, at no position is there a letter strictly greater than target[p] still available (we only have a and b). p drops below 0, so the answer is "".

Complexity

• Time: O(n · 26). Each of the n break positions scans at most 26 letters; the final tail build is O(n + 26).
• Space: O(n) for the prefix and the constructed answer (the count array is O(26)).

class Solution {
    public String lexGreaterPermutation(String s, String target) {
        int n = s.length();
        int[] cnt = new int[26];
        for (int k = 0; k < n; k++) cnt[s.charAt(k) - 'a']++;

        // Greedily match target's prefix while the letters are available.
        char[] prefix = new char[n];
        int i = 0;
        while (i < n && cnt[target.charAt(i) - 'a'] > 0) {
            cnt[target.charAt(i) - 'a']--;
            prefix[i] = target.charAt(i);
            i++;
        }

        // Try to "break" at position p; if impossible, restore the letter matched
        // just before p and try to break there instead.
        int p = i;
        while (p >= 0) {
            if (p < n) {
                int t = target.charAt(p) - 'a';
                for (int c = t + 1; c < 26; c++) {
                    if (cnt[c] > 0) {
                        cnt[c]--;
                        StringBuilder sb = new StringBuilder();
                        for (int k = 0; k < p; k++) sb.append(prefix[k]);
                        sb.append((char) ('a' + c));
                        for (int cc = 0; cc < 26; cc++)
                            for (int r = 0; r < cnt[cc]; r++) sb.append((char) ('a' + cc));
                        return sb.toString();
                    }
                }
            }
            p--;
            if (p >= 0) cnt[target.charAt(p) - 'a']++;
        }

        return "";
    }
}