Lexicographically Smallest String After Deleting Duplicate Characters solution and explanation
3 more videos on this problem
Lexicographically Smallest String After Deleting Duplicate Characters 🔥 LeetCode 3816 | Optimal Study Placement · 27:49 · 548 views
Leetcode 3816 | Lexicographically Smallest String After Deleting Duplicate CharactersCodeWithMeGuys · 17:10 · 340 views
3816. Lexicographically Smallest String After Deleting Duplicate Characters (Leetcode Hard)Programming Live with Larry · 34:11 · 311 views
LeetCode 3816 | Lexicographically Smallest String After Deleting Duplicates | Stack + Greedyhidden testcase · 24:03 · 85 views
The problem
You are given a string s that consists of lowercase English letters.
You can perform the following operation any number of times (possibly zero times):
- Choose any letter that appears at least twice in the current string
sand delete any one occurrence.
Return the lexicographically smallest resulting string that can be formed this way.
Example 1:
Input: s = "aaccb"
Output: "aacb"
Explanation:
We can form the strings "acb", "aacb", "accb", and "aaccb". "aacb" is the lexicographically smallest one.
For example, we can obtain "aacb" by choosing 'c' and deleting its first occurrence.
Example 2:
Input: s = "z"
Output: "z"
Explanation:
We cannot perform any operations. The only string we can form is "z".
Constraints:
1 <= s.length <= 105scontains lowercase English letters only.
Approach overview
Problem Overview: Given a string, remove duplicate characters so every character appears exactly once while keeping the result lexicographically smallest. The relative order of characters must remain valid based on the original string.
Approach 1: Brute Force with Backtracking (Exponential Time, O(2^n) time, O(n) space)
Generate all subsequences that contain unique characters and keep the lexicographically smallest valid result. Use a set to ensure characters appear only once in the candidate string and recursively explore include/exclude decisions. Each subsequence must also maintain original ordering since it's derived directly from the input. This approach demonstrates the problem constraints but quickly becomes infeasible for larger strings because the search space grows exponentially.
Approach 2: Greedy Monotonic Stack (Optimal) (O(n) time, O(n) space)
The optimal solution uses a stack combined with greedy decisions. First record the last occurrence index of each character using a hash table. Iterate through the string and maintain a stack representing the current result. If the current character is smaller than the stack's top and the top character appears later again in the string, pop it to make the result lexicographically smaller. Push the current character if it hasn't already been used. A visited set ensures each character appears once, and the stack naturally forms the smallest lexicographic sequence.
This works because characters that appear again later can safely be removed from the stack if a smaller character appears earlier in the result. The stack therefore behaves like a monotonic stack that maintains the best possible lexicographic ordering while guaranteeing every character is included exactly once.
Recommended for interviews: Interviewers expect the greedy monotonic stack solution with last-occurrence tracking. Brute force demonstrates understanding of the constraint space, but the O(n) stack approach shows strong algorithmic reasoning and familiarity with stack-based greedy optimization patterns.
Solution
We can use a stack stk to store the characters of the result string, and a hash table cnt to record the number of occurrences of each character in string s.
First, we initialize cnt to count the occurrences of each character in string s. Then, we iterate through each character c in string s:
- If the stack is not empty, the top character of the stack is greater than
c, and the top character will appear again in strings, we pop the top character and decrement its count incnt. - Push character
cinto the stack.
Finally, if there are duplicate characters in the stack, we continue to pop the top character until the count of the top character in cnt is 1.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
class Solution:
def lexSmallestAfterDeletion(self, s: str) -> str:
cnt = Counter(s)
stk = []
for c in s:
while stk and stk[-1] > c and cnt[stk[-1]] > 1:
cnt[stk.pop()] -= 1
stk.append(c)
while stk and cnt[stk[-1]] > 1:
cnt[stk.pop()] -= 1
return "".join(stk)class Solution {
public String lexSmallestAfterDeletion(String s) {
int[] cnt = new int[26];
int n = s.length();
for (int i = 0; i < n; ++i) {
++cnt[s.charAt(i) - 'a'];
}
StringBuilder stk = new StringBuilder();
for (int i = 0; i < n; ++i) {
char c = s.charAt(i);
while (stk.length() > 0 && stk.charAt(stk.length() - 1) > c
&& cnt[stk.charAt(stk.length() - 1) - 'a'] > 1) {
--cnt[stk.charAt(stk.length() - 1) - 'a'];
stk.setLength(stk.length() - 1);
}
stk.append(c);
}
while (cnt[stk.charAt(stk.length() - 1) - 'a'] > 1) {
--cnt[stk.charAt(stk.length() - 1) - 'a'];
stk.setLength(stk.length() - 1);
}
return stk.toString();
}
}class Solution {
public:
string lexSmallestAfterDeletion(string s) {
int cnt[26]{};
for (char c : s) {
++cnt[c - 'a'];
}
string stk;
for (char c : s) {
while (stk.size() && stk.back() > c && cnt[stk.back() - 'a'] > 1) {
--cnt[stk.back() - 'a'];
stk.pop_back();
}
stk.push_back(c);
}
while (cnt[stk.back() - 'a'] > 1) {
--cnt[stk.back() - 'a'];
stk.pop_back();
}
return stk;
}
};function lexSmallestAfterDeletion(s: string): string {
const cnt: number[] = new Array(26).fill(0);
const n = s.length;
const a = 'a'.charCodeAt(0);
for (let i = 0; i < n; ++i) {
++cnt[s.charCodeAt(i) - a];
}
const stk: string[] = [];
for (let i = 0; i < n; ++i) {
const c = s[i];
while (
stk.length > 0 &&
stk[stk.length - 1] > c &&
cnt[stk[stk.length - 1].charCodeAt(0) - a] > 1
) {
--cnt[stk.pop()!.charCodeAt(0) - a];
}
stk.push(c);
}
while (cnt[stk[stk.length - 1].charCodeAt(0) - a] > 1) {
--cnt[stk.pop()!.charCodeAt(0) - a];
}
return stk.join('');
}func lexSmallestAfterDeletion(s string) string {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
stk := []byte{}
for _, c := range s {
for len(stk) > 0 && stk[len(stk)-1] > byte(c) && cnt[stk[len(stk)-1]-'a'] > 1 {
cnt[stk[len(stk)-1]-'a']--
stk = stk[:len(stk)-1]
}
stk = append(stk, byte(c))
}
for cnt[stk[len(stk)-1]-'a'] > 1 {
cnt[stk[len(stk)-1]-'a']--
stk = stk[:len(stk)-1]
}
return string(stk)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Backtracking | O(2^n) | O(n) | Understanding the full search space or validating small inputs |
| Greedy Monotonic Stack | O(n) | O(n) | Optimal solution for production and interviews; works for large strings |
Frequently asked questions
Is Lexicographically Smallest String After Deleting Duplicate Characters easy or hard?
The problem is considered Hard because it requires combining greedy decisions with a monotonic stack and last-occurrence tracking. Many candidates initially attempt brute force or sorting-based approaches before recognizing the linear-time greedy pattern.
Lexicographically Smallest String After Deleting Duplicate Characters Python/Java solution
Implement the greedy monotonic stack algorithm. Track the last index of each character, maintain a stack for the result, and a visited set to avoid duplicates. The same logic works across Python, Java, C++, Go, and TypeScript with O(n) time complexity.
How to solve Lexicographically Smallest String After Deleting Duplicate Characters in O(n)?
Store the last index of each character, then iterate through the string while maintaining a stack and a visited set. If the current character is smaller than the stack top and the stack top appears later again, pop the stack. Push the current character if it hasn't already been used. This greedy process guarantees the smallest lexicographic result in linear time.
What is the best approach for Lexicographically Smallest String After Deleting Duplicate Characters?
The optimal approach uses a greedy monotonic stack with last-occurrence tracking. While iterating through the string, characters are pushed to a stack while maintaining lexicographic order. If a larger character appears earlier and also occurs later in the string, it can be safely popped to produce a smaller result. This algorithm runs in O(n) time with O(n) space.
Is Lexicographically Smallest String After Deleting Duplicate Characters asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests greedy reasoning, stack usage, and string manipulation. It is closely related to classic problems such as "Remove Duplicate Letters" that are commonly used in technical interviews.
What data structure is used in Lexicographically Smallest String After Deleting Duplicate Characters?
The primary data structure is a stack used as a monotonic structure to maintain lexicographic order. A hash table tracks the last occurrence of each character, and a set tracks which characters are already included in the result.
What is the time complexity of Lexicographically Smallest String After Deleting Duplicate Characters?
The optimal monotonic stack solution runs in O(n) time where n is the length of the string. Each character is pushed and popped from the stack at most once. Space complexity is O(n) due to the stack, visited set, and last-occurrence map.