Lexicographically Smallest Permutation Greater Than Target solution and explanation
Google
6 more videos on this problem
Lexicographically Smallest Permutation Greater Than Target | LeetCode 3720 | Weekly Contest 472Sanyam IIT Guwahati · 17:51 · 2K views
Leetcode 3720 | Lexicographically Smallest Permutation Greater Than Target | Weekly Contest 472Samrat Bhardwaj · 44:52 · 917 views
3720. Lexicographically Smallest Permutation Greater Than Target (Leetcode Medium)Programming Live with Larry · 35:15 · 591 views
Weekly Contest 472 🔥 Lexicographically Smallest Permutation Greater Than Target | Leetcode 3720 Study Placement · 19:28 · 487 views
Leetcode 3720 | Lexicographically Smallest Permutation Greater Than TargetCodeWithMeGuys · 17:22 · 428 views
Leetcode 3720: Lexicographically Smallest Permutation Greater Than TargetJash Rashne · 40:31 · 177 views
Q3 - Lexicographically Smallest Permutation Greater Than Target - C# SolutionAxoryn · 2:08 · 112 views
The problem
You are given two strings s and target, both having length n, consisting of lowercase English letters.
Return the lexicographically smallest permutation of s that is strictly greater than target. If no permutation of s is lexicographically strictly greater than target, return an empty string.
A string a is lexicographically strictly greater than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b.
Example 1:
Input: s = "abc", target = "bba"
Output: "bca"
Explanation:
- The permutations of
s(in lexicographical order) are"abc","acb","bac","bca","cab", and"cba". - The lexicographically smallest permutation that is strictly greater than
targetis"bca".
Example 2:
Input: s = "leet", target = "code"
Output: "eelt"
Explanation:
- The permutations of
s(in lexicographical order) are"eelt","eetl","elet","elte","etel","etle","leet","lete","ltee","teel","tele", and"tlee". - The lexicographically smallest permutation that is strictly greater than
targetis"eelt".
Example 3:
Input: s = "baba", target = "bbaa"
Output: ""
Explanation:
- The permutations of
s(in lexicographical order) are"aabb","abab","abba","baab","baba", and"bbaa". - None of them is lexicographically strictly greater than
target. Therefore, the answer is"".
Constraints:
1 <= s.length == target.length <= 300sandtargetconsist of only lowercase English letters.
Approach overview
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.
Solution
impl Solution {
pub fn lex_greater_permutation(s: String, target: String) -> String {
let mut permutation = s.into_bytes();
let target_bytes = target.as_bytes();
let mut letter_counts = [0usize; 26];
for &byte in &permutation {
letter_counts[(byte - b'a') as usize] += 1;
}
let mut prefix_length = 0;
while prefix_length < target_bytes.len() {
let target_letter = (target_bytes[prefix_length] - b'a') as usize;
if letter_counts[target_letter] == 0 {
break;
}
permutation[prefix_length] = target_bytes[prefix_length];
letter_counts[target_letter] -= 1;
prefix_length += 1;
}
loop {
if prefix_length < target_bytes.len() {
let next_letter = (target_bytes[prefix_length] - b'a') as usize + 1;
if let Some(replacement_letter) =
(next_letter..26).find(|&letter| letter_counts[letter] > 0)
{
permutation[prefix_length] = b'a' + replacement_letter as u8;
letter_counts[replacement_letter] -= 1;
let mut write_index = prefix_length + 1;
for (letter, &count) in letter_counts.iter().enumerate() {
for _ in 0..count {
permutation[write_index] = b'a' + letter as u8;
write_index += 1;
}
}
return String::from_utf8(permutation).unwrap();
}
}
if prefix_length == 0 {
return String::new();
}
prefix_length -= 1;
letter_counts[(target_bytes[prefix_length] - b'a') as usize] += 1;
}
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation Enumeration | O(n! * n) | O(n) | Only for very small inputs or conceptual understanding |
| Backtracking with Pruning | O(n!) worst case | O(n) | When exploring permutations but pruning invalid prefixes |
| Greedy Prefix Construction with Counting | O(n * k) | O(k) | General case; optimal for interviews and large inputs |
Frequently asked questions
Is Lexicographically Smallest Permutation Greater Than Target easy or hard?
The problem is typically rated Medium because it requires combining greedy reasoning with lexicographic ordering and frequency counting. The tricky part is maintaining the prefix constraint relative to the target while ensuring the final permutation is the smallest possible valid result.
Lexicographically Smallest Permutation Greater Than Target Python/Java solution
Implement the greedy strategy with a frequency map (dictionary in Python or array/map in Java). Iterate through the target string, try candidate characters greater than or equal to the current target character, and simulate placing them while updating counts. When a strictly larger character is chosen, append the remaining characters in sorted order to produce the smallest valid permutation.
How to solve Lexicographically Smallest Permutation Greater Than Target in O(n)?
A near linear solution is achieved by scanning the string once while maintaining a frequency count of remaining characters. For each position, attempt characters in sorted order and check whether placing one keeps the prefix valid relative to the target. After placing a character larger than the target at that position, fill the rest with the smallest remaining characters.
What is the best approach for Lexicographically Smallest Permutation Greater Than Target?
The best approach uses a greedy prefix construction combined with a character frequency map. At each index, try the smallest possible character that keeps the resulting prefix capable of exceeding the target. Once a character larger than the target's current character is placed, fill the remaining positions with the smallest available characters. This runs in O(n * k) time where k is the alphabet size.
Is Lexicographically Smallest Permutation Greater Than Target asked at Google/Amazon/Meta?
Problems involving lexicographic permutation construction, greedy prefix decisions, and counting arrays are common in interviews at companies like Google, Amazon, and Meta. Variants appear in string manipulation and greedy design rounds where candidates must construct the next valid lexicographic configuration efficiently.
What data structure is used in Lexicographically Smallest Permutation Greater Than Target?
The solution typically uses a hash table or counting array to track the frequency of each character that can still be placed. This allows constant-time updates when characters are used and enables quick iteration through the remaining characters in lexicographic order.
What is the time complexity of Lexicographically Smallest Permutation Greater Than Target?
The optimal greedy solution runs in O(n * k) time and O(k) space. Here n is the string length and k is the number of distinct characters (often 26 for lowercase letters). Brute force permutation generation would take O(n! * n) time, which is infeasible for larger inputs.