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):
s and 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 <= 105s contains lowercase English letters only.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.
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:
c, and the top character will appear again in string s, we pop the top character and decrement its count in cnt.c into 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.
Python
Java
C++
Go
TypeScript
| 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 |
Lexicographically Smallest String After Deleting Duplicate Characters 🔥 LeetCode 3816 | Optimal • Study Placement • 489 views views
Watch 3 more video solutions →Practice Lexicographically Smallest String After Deleting Duplicate Characters with our built-in code editor and test cases.
Practice on FleetCode