Remove Duplicate Letters
MedPrompt
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: s = "bcabc"
Output: "abc"Example 2:
Input: s = "cbacdcbc"
Output: "acdb"
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
Approaches
2 approaches with complexity analysis and trade-offs.
This approach generates all possible subsequences that contain each character exactly once, then finds the lexicographically smallest one among them.
Algorithm
- Find all unique characters in the string
- Generate all possible subsequences using recursion
- Filter subsequences that contain each unique character exactly once
- Sort all valid subsequences lexicographically
- Return the first (smallest) subsequence
Walkthrough
The brute force approach involves generating all possible subsequences of the string that contain each unique character exactly once. For each subsequence, we check if it contains all unique characters from the original string exactly once. Among all valid subsequences, we return the lexicographically smallest one.
public String removeDuplicateLetters(String s) { Set<Character> uniqueChars = new HashSet<>(); for (char c : s.toCharArray()) { uniqueChars.add(c); } List<String> validSubsequences = new ArrayList<>(); generateSubsequences(s, 0, new StringBuilder(), uniqueChars, validSubsequences); Collections.sort(validSubsequences); return validSubsequences.get(0);} private void generateSubsequences(String s, int index, StringBuilder current, Set<Character> required, List<String> result) { if (index == s.length()) { if (current.length() == required.size() && containsAllRequired(current.toString(), required)) { result.add(current.toString()); } return; } // Include current character current.append(s.charAt(index)); generateSubsequences(s, index + 1, current, required, result); current.deleteCharAt(current.length() - 1); // Exclude current character generateSubsequences(s, index + 1, current, required, result);}Complexity
Time
O(2^n * n) where n is the length of string - exponential time due to generating all subsequences
Space
O(2^n * n) for storing all possible subsequences
Trade-offs
Pros
Simple to understand and implement
Guaranteed to find the correct answer
No complex data structures required
Cons
Extremely inefficient for large inputs
Exponential time and space complexity
Not practical for real-world applications
Will cause timeout for most test cases
This approach uses a stack-based greedy algorithm to build the lexicographically smallest result by making optimal local decisions.
Algorithm
- Count frequency of each character in the string
- Use a stack to build the result and a boolean array to track included characters
- For each character in the string:
- Decrease its count
- Skip if already included in result
- Remove characters from stack top if current char is smaller and removed char appears later
- Add current character to stack and mark as included
- Convert stack to string and return
Walkthrough
The optimal approach uses a stack to build the result string while ensuring lexicographical order. We iterate through the string and for each character, we decide whether to include it immediately or wait for a better position. The key insight is that we can remove a character from our current result if:
- The current character is smaller than the last character in our result
- The last character appears later in the string
- The last character is not already in our final result
public String removeDuplicateLetters(String s) { // Count frequency of each character int[] count = new int[26]; for (char c : s.toCharArray()) { count[c - 'a']++; } // Track which characters are already in result boolean[] inResult = new boolean[26]; Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { // Decrease count as we process the character count[c - 'a']--; // If character is already in result, skip it if (inResult[c - 'a']) { continue; } // Remove characters from stack if: // 1. Current char is smaller than stack top // 2. Stack top appears later in string (count > 0) while (!stack.isEmpty() && c < stack.peek() && count[stack.peek() - 'a'] > 0) { char removed = stack.pop(); inResult[removed - 'a'] = false; } // Add current character to result stack.push(c); inResult[c - 'a'] = true; } // Build result string from stack StringBuilder result = new StringBuilder(); for (char c : stack) { result.append(c); } return result.toString();}Complexity
Time
O(n) where n is the length of string - each character is pushed and popped at most once
Space
O(1) or O(26) for the arrays and stack, which is constant space
Trade-offs
Pros
Optimal time and space complexity
Elegant greedy approach
Single pass through the string
Uses efficient data structures
Cons
Requires understanding of greedy algorithms
Logic for when to remove characters can be tricky to grasp
Need to carefully track character frequencies and inclusion status
Solutions
Solution
class Solution {public String removeDuplicateLetters(String s) { int n = s.length(); int[] last = new int[26]; for (int i = 0; i < n; ++i) { last[s.charAt(i) - 'a'] = i; } Deque<Character> stk = new ArrayDeque<>(); int mask = 0; for (int i = 0; i < n; ++i) { char c = s.charAt(i); if (((mask >> (c - 'a')) & 1) == 1) { continue; } while (!stk.isEmpty() && stk.peek() > c && last[stk.peek() - 'a'] > i) { mask ^= 1 << (stk.pop() - 'a'); } stk.push(c); mask |= 1 << (c - 'a'); } StringBuilder ans = new StringBuilder(); for (char c : stk) { ans.append(c); } return ans.reverse().toString(); }}class Solution {public: string removeDuplicateLetters(string s) { int n = s.size(); int last[26] = {0}; for (int i = 0; i < n; ++i) { last[s[i] - 'a'] = i; } string ans; int mask = 0; for (int i = 0; i < n; ++i) { char c = s[i]; if ((mask >> (c - 'a')) & 1) { continue; } while (!ans.empty() && ans.back() > c && last[ans.back() - 'a'] > i) { mask ^= 1 << (ans.back() - 'a'); ans.pop_back(); } ans.push_back(c); mask |= 1 << (c - 'a'); } return ans; }};class Solution: def removeDuplicateLetters(self, s: str) -> str: last = {c: i for i, c in enumerate(s)} stk = [] vis = set() for i, c in enumerate(s): if c in vis: continue while stk and stk[- 1] > c and last[stk[- 1]] > i: vis . remove(stk . pop()) stk . append(c) vis . add(c) return '' . join(stk)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.