Lexicographically Smallest Permutation Greater Than Target

Lexicographically Smallest Permutation Greater Than Target

What is this problem about?

The "Lexicographically Smallest Permutation Greater Than Target interview question" is a variation of the "Next Permutation" problem. You are given a source string and a target string. You need to find the lexicographically smallest permutation of the source string that is strictly larger than the target. If no such permutation exists, return -1. This "Lexicographically Smallest Permutation Greater Than Target coding problem" requires a combination of counting and greedy construction.

Why is this asked in interviews?

This problem is asked at companies like Amazon to test a candidate's mastery of the "Greedy interview pattern" and "Counting interview pattern". It is more complex than a standard next permutation because the source and target might be different strings entirely, meaning you must manage a fixed pool of characters (the source) to outpace the target.

Algorithmic pattern used

The approach is to find the longest common prefix between your construction and the target. At some index i, you must place a character from your remaining pool that is strictly greater than target[i]. To keep the result lexicographically smallest, you pick the smallest character in your pool that is greater than target[i]. After this "diversion," you fill the remaining positions with the remaining characters in ascending order.

Example explanation

Source: "abc", Target: "acb"

1. Try prefix "a": Next target char is 'c'. In our remaining pool {b, c}, is there a char > 'c'? No.
2. Backtrack to index 0: In our pool {a, b, c}, is there a char > 'a'? Yes, 'b'.
3. Place 'b': String starts with "b". Remaining pool: {a, c}.
4. Fill greedily: To keep it smallest, place 'a' then 'c'. Result: "bac".

Common mistakes candidates make

• Using standard "Next Permutation": Forgetting that the source characters are fixed and might not be the same as the target's characters.
• O(n!) brute force: Generating all permutations and sorting them, which is impossible for longer strings.
• Incorrect fill: Forgetting to sort the remaining characters in ascending order after the first character that differs from the target.

Interview preparation tip

When building a string to be "just barely larger" than another, think about the first point of difference. Everything after that point should be as small as possible to keep the overall string as small as possible while still maintaining the "greater than" condition.