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
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(); }}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.