3720. Lexicographically Smallest Permutation Greater Than Target

String
Greedy
Counting
Sorting

TIME

O(26 * n)

SPACE

O(n)

Intuition

Only the multiset of letters in s matters, since any arrangement is allowed. Every candidate answer has the same shape:

target[0..p-1]  +  c  +  (everything left over, sorted ascending)

where the first p characters copy target exactly, c is strictly greater than target[p], and the tail is sorted to make the suffix as small as possible.

A longer shared prefix is always better. Suppose one candidate deviates at position p and another at an earlier p' < p. At index p', the first candidate holds target[p'] while the second holds something strictly greater, so the first is smaller, regardless of what follows. Hence: maximize p.

That gives a clean search order, find the longest prefix of target that s's letters can actually spell, then walk p downward until a valid deviation character exists.

Approach

Count the letters of s into a 26-slot array.
Longest match: walk target left to right, consuming target[i] from the counts while it is available. Let maxMatch be how far this got.
Search p from maxMatch down to 0:
- Keep the counts in sync, moving from p+1 to p means returning target[p] to the pool.
- Skip p == n (a full match leaves no position to raise, and equal is not "strictly greater").
- Look for the smallest available letter c > target[p]. If one exists, consume it and return target[:p] + c + <remaining letters in ascending order>.
If no p yields a deviation, return "".

Complexity

Time: O(26n), each p scans at most 26 letters, plus O(n) to emit the answer
Space: O(n), the counts array and the output string

Edge Cases

s can spell target exactly (maxMatch == n) → must still deviate earlier, so start the search at p = n - 1 (Example 3 exhausts every p and returns "")
The largest permutation of s is <= target → ""
Deviating at p = 0 is valid when the smallest letter greater than target[0] exists (Example 2)
Duplicate letters are handled naturally by counts rather than a set
The tail must be sorted ascending, not left in input order

Code

class Solution:
    def smallestPermutation(self, s: str, target: str) -> str:
        """
        3720. Lexicographically Smallest Permutation Greater Than Target
        Time: O(26 * n)
        Space: O(n)
        """
        n = len(s)
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - 97] += 1

        # Longest prefix of target that s's letters can spell.
        matched = 0
        while matched < n and counts[ord(target[matched]) - 97] > 0:
            counts[ord(target[matched]) - 97] -= 1
            matched += 1

        # Prefer the longest shared prefix: deviating later gives a smaller result.
        for p in range(matched, -1, -1):
            # Roll characters back into the pool until counts match a prefix of length p.
            while matched > p:
                matched -= 1
                counts[ord(target[matched]) - 97] += 1

            if p >= n:
                continue  # a full match is equal, not strictly greater

            # Smallest available letter strictly greater than target[p].
            for c in range(ord(target[p]) - 97 + 1, 26):
                if counts[c] > 0:
                    counts[c] -= 1
                    rest = "".join(chr(97 + j) * counts[j] for j in range(26))
                    return target[:p] + chr(97 + c) + rest

        return ""

/**
 * 3720. Lexicographically Smallest Permutation Greater Than Target
 * Time: O(26 * n)
 * Space: O(n)
 */
class Solution {
    public String smallestPermutation(String s, String target) {
        int n = s.length();
        int[] counts = new int[26];
        for (int i = 0; i < n; i++) {
            counts[s.charAt(i) - 'a']++;
        }

        // Longest prefix of target that s's letters can spell.
        int matched = 0;
        while (matched < n && counts[target.charAt(matched) - 'a'] > 0) {
            counts[target.charAt(matched) - 'a']--;
            matched++;
        }

        // Prefer the longest shared prefix: deviating later gives a smaller result.
        for (int p = matched; p >= 0; p--) {
            // Roll characters back into the pool until counts match a prefix of length p.
            while (matched > p) {
                matched--;
                counts[target.charAt(matched) - 'a']++;
            }

            if (p >= n) {
                continue; // a full match is equal, not strictly greater
            }

            // Smallest available letter strictly greater than target[p].
            for (int c = target.charAt(p) - 'a' + 1; c < 26; c++) {
                if (counts[c] > 0) {
                    counts[c]--;
                    StringBuilder sb = new StringBuilder();
                    sb.append(target, 0, p);
                    sb.append((char) ('a' + c));
                    for (int j = 0; j < 26; j++) {
                        for (int t = 0; t < counts[j]; t++) {
                            sb.append((char) ('a' + j));
                        }
                    }
                    return sb.toString();
                }
            }
        }

        return "";
    }
}