Least Permutation Strictly Above a Target

### Problem You are given strings `s` and `target` of the same length, containing only lowercase English letters. Return the lexicographically smallest permutation of `s` that is **strictly greater** than `target`. If no such permutation exists, return an empty string. For equal-length strings, lexicographic order is decided at the first position where their letters differ. The string with the later alphabet letter at that position is greater. A permutation must use every character of `s` exactly as many times as it appears. ```cpp class Solution { public: string lexGreaterPermutation(string s, string target); }; ``` ### Examples **Example 1:** ```text Input: s = "aabc", target = "abca" Output: "acab" Explanation: The result uses two a's, one b, and one c. It is greater than "abca" at the second position, and no smaller permutation is strictly greater than the target. Returning "abca" itself would not satisfy strictness. ``` **Example 2:** ```text Input: s = "aac", target = "caa" Output: "" Explanation: The distinct permutations are "aac", "aca", and "caa". None is strictly greater than "caa". ``` ### Constraints - `1 <= s.length == target.length <= 300`. - Both strings consist only of lowercase English letters. ### Clarifying Questions - Must `target` itself be a permutation of `s`? No. - May repeated letters in `s` be discarded? No. The result must preserve the full character multiset. - Is an equal result acceptable? No; the comparison is strict. - Does an empty result mean the input strings were empty? No. Inputs are nonempty; an empty result reports that no valid greater permutation exists. ### What a Strong Answer Covers - Exact character multiplicities and the first-differing-position comparison. - Both strict inequality and minimality among all valid greater permutations. - Repeated characters, a one-character input, and the no-result case. - A completeness argument and bounds for the full string length. ### Follow-up Questions - How would allowing equality change the acceptance condition? - What would need to be added to the order definition if strings of different lengths were compared? ```hint Keep the equal prefix reversible Match the target while possible. To become greater, use the smallest available larger letter at a position, then make the remaining suffix as small as possible. If that cannot be done at the current position, restore the last matched character and try an earlier position. A completely matched target still needs this strict-successor step. ```