Lexicographically Smallest Permutation Greater Than Target - Solution & Explanation

Problem Overview: Given a set of characters (or a string whose characters can be rearranged) and a target string, build the lexicographically smallest permutation that is still strictly greater than the target. If multiple permutations exist, return the smallest one in lexicographic order. The difficulty comes from respecting both the remaining character counts and the lexicographic constraint.

Approach 1: Brute Force Enumeration (O(n! * n) time, O(n) space)

Generate every permutation of the characters, compare each permutation with the target, and keep the smallest permutation that is greater than it. Each generated string requires a lexicographic comparison, which takes O(n). This approach works only for very small inputs because permutations grow factorially. It demonstrates the core requirement of the problem but is impractical for interviews or production constraints.

Approach 2: Backtracking with Pruning (O(n! ) worst case, O(n) space)

Use backtracking with a frequency map to generate permutations in lexicographic order. As soon as a permutation becomes smaller than the prefix of the target where it must be larger, prune that branch. This reduces unnecessary exploration compared to full enumeration. A hash table or counting array tracks remaining characters. Although pruning helps in practice, the worst‑case complexity is still factorial.

Approach 3: Greedy Prefix + Counting (O(n * k) time, O(k) space)

The optimal solution builds the answer from left to right. First count the frequency of each character using a hash table. At position i, try placing the smallest available character that keeps the prefix lexicographically valid. If the prefix is still equal to the target, you must try characters greater than or equal to target[i]. When you place a character strictly greater than target[i], the rest of the string can be filled with the smallest remaining characters in sorted order. This greedy construction relies on greedy choice and character string ordering. The alphabet size k is typically small (e.g., 26), giving an efficient O(n * k) solution.

Recommended for interviews: The greedy counting approach is what interviewers expect. It shows you understand lexicographic ordering and how to construct permutations without enumerating all possibilities. Mentioning the brute force or backtracking ideas briefly helps demonstrate the progression from naive enumeration to an efficient greedy construction.