Code Implementation

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last_index = {c: i for i, c in enumerate(s)}
        stack = []
        seen = set()
        for i, c in enumerate(s):
            if c in seen:
                continue
            while stack and c < stack[-1] and i < last_index[stack[-1]]:
                seen.remove(stack.pop())
            stack.append(c)
            seen.add(c)
        return ''.join(stack)
      

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> lastIndex(26, -1);
        for (int i = 0; i < s.size(); ++i)
            lastIndex[s[i] - 'a'] = i;
        vector<bool> seen(26, false);
        string stack = "";
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (seen[c - 'a']) continue;
            while (!stack.empty() && c < stack.back() && i < lastIndex[stack.back() - 'a']) {
                seen[stack.back() - 'a'] = false;
                stack.pop_back();
            }
            stack.push_back(c);
            seen[c - 'a'] = true;
        }
        return stack;
    }
};
      

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i++)
            lastIndex[s.charAt(i) - 'a'] = i;
        boolean[] seen = new boolean[26];
        StringBuilder stack = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen[c - 'a']) continue;
            while (stack.length() > 0 && c < stack.charAt(stack.length() - 1)
                    && i < lastIndex[stack.charAt(stack.length() - 1) - 'a']) {
                seen[stack.charAt(stack.length() - 1) - 'a'] = false;
                stack.deleteCharAt(stack.length() - 1);
            }
            stack.append(c);
            seen[c - 'a'] = true;
        }
        return stack.toString();
    }
}
      

var removeDuplicateLetters = function(s) {
    const lastIndex = {};
    for (let i = 0; i < s.length; i++) {
        lastIndex[s[i]] = i;
    }
    const stack = [];
    const seen = new Set();
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (seen.has(c)) continue;
        while (stack.length && c < stack[stack.length - 1] && i < lastIndex[stack[stack.length - 1]]) {
            seen.delete(stack.pop());
        }
        stack.push(c);
        seen.add(c);
    }
    return stack.join('');
};
      

Problem Description

Given a string s consisting of only lowercase English letters, 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.

• Return the answer as a string.
• Each letter may only be used once in the result.
• There is exactly one valid solution for each input.

Example:
Input: s = "bcabc"
Output: "abc"

Thought Process

At first glance, it seems we could simply remove duplicates by using a set. However, this would not guarantee the smallest lexicographical order. For example, for s = "cbacdcbc", a set would give us "cbad" (in order of appearance), but the correct answer is "acdb".

The brute-force approach would be to generate all unique permutations of the string's letters and pick the lexicographically smallest one. But this is highly inefficient, especially for longer strings.

We need to find a way to always pick the smallest possible character at every step, while ensuring that all other characters can still appear later if we skip them now. This leads us to a greedy and stack-based approach.

Solution Approach

The optimized solution uses a monotonic stack and keeps track of the last occurrence of each character. Here is how it works:

1. Track Last Occurrences:
   • First, record the last index where each character appears in the string. This helps us know if it's safe to remove a character now and add it later.
2. Use a Stack:
   • We use a stack to build our answer. The stack helps us maintain the relative order and allows us to remove previously added characters if we encounter a smaller character and the removed character will appear again later.
3. Seen Set:
   • We keep a set (or boolean array) to know if a character is already in the stack, so we don't add it twice.
4. Iterate and Decide:
   • For each character, if it's already in the stack, skip it.
   • If not, check the top of the stack: while the stack is not empty, and the current character is smaller than the stack's top, and the top character will occur later, pop the top character from the stack and mark it as not seen.
   • Finally, push the current character onto the stack and mark it as seen.
5. Build the Result:
   • At the end, join the stack to form the result string.

This method ensures that we always get the smallest lexicographical order, use each letter only once, and preserve the relative order as much as possible.

Example Walkthrough

Let's walk through the input s = "cbacdcbc":

1. Last Occurrences: c:7, b:6, a:2, d:5
2. Step-by-step:
   • Stack: [], Seen: {}
     i=0, c: Not in seen. Stack is empty. Push c. Stack: [c]
   • i=1, b: Not in seen. b < c, and c appears again at i=7. Pop c. Stack: []. Push b. Stack: [b]
   • i=2, a: Not in seen. a < b, and b appears again at i=6. Pop b. Stack: []. Push a. Stack: [a]
   • i=3, c: Not in seen. c > a. Push c. Stack: [a, c]
   • i=4, d: Not in seen. d > c. Push d. Stack: [a, c, d]
   • i=5, c: Already in seen. Skip.
   • i=6, b: Not in seen. b < d, but d does not appear again. b < c, but c appears again. So, pop d (cannot, d doesn't appear again), so keep d. Push b. Stack: [a, c, d, b]
   • i=7, c: Already in seen. Skip.
3. Result: Join stack to get "acdb".

Time and Space Complexity

• Brute-force approach:
  • Time: O(n! * n) (generating all permutations and checking for uniqueness)
  • Space: O(n!) for all permutations
• Optimized stack-based approach:
  • Time: O(n), where n is the length of the string. Each character is pushed and popped at most once.
  • Space: O(1) (since the alphabet is fixed at 26 lowercase letters, stack and seen set sizes are bounded), plus O(n) for the output.

Summary

The key insight is to use a greedy, stack-based approach: always pick the smallest character possible while ensuring that all other necessary characters can still be chosen later. By tracking last occurrences and using a stack to maintain order, we efficiently build the smallest lexicographical string with unique letters. This method is elegant, fast, and leverages the properties of the problem for an optimal solution.