Lexicographically Smallest String After Deleting Duplicate Characters - Video Solutions
Lexicographically Smallest String After Deleting Duplicate Characters 🔥 LeetCode 3816 | Optimal
Lexicographically Smallest String After Deleting Duplicate Characters - Video Solution
Watch 4 video solutions for Lexicographically Smallest String After Deleting Duplicate Characters, a hard level problem involving Hash Table, String, Stack. This walkthrough by Study Placement has 548 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
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 |