Remove Duplicate Letters

MEDIUM

Description

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 <= 10⁴
s consists of lowercase English letters.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Approaches

Checkout 2 different approaches to solve Remove Duplicate Letters. Click on different approaches to view the approach and algorithm in detail.

Brute Force - Generate All Subsequences

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

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 Analysis

Time Complexity: O(2^n * n) where n is the length of string - exponential time due to generating all subsequencesSpace Complexity: O(2^n * n) for storing all possible subsequences

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Remove Duplicate Letters. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Remove Duplicate Letters

Patterns:

Greedy

Data Structures:

StringStackMonotonic Stack

Companies:

ByteDance |Expedia |Goldman Sachs |DRW |