LeetCode 316 Remove Duplicate Letters

Problem Overview

• LeetCode 316 Remove Duplicate Letters

Remove duplicate letters from a string such that every letter appears exactly once, and the result is the lexicographically smallest possible string.

Algorithm Breakdown

Step 1: Track Last Occurrence

int[] lastIndex = new int[26];
for (int i = 0; i < s.length(); i++){
    lastIndex[s.charAt(i) - 'a'] = i;
}

This records the last position where each character appears. This is crucial for deciding whether we can safely remove a character.

Step 2: Greedy Stack Construction

The core insight is using a monotonic stack to maintain lexicographically smallest order:

while (!st.isEmpty() && st.peek() > curindex && i < lastIndex[st.peek()]) {
    seen[st.pop()] = false;
}

Key conditions for popping from stack:

1. st.peek() > curindex - Previous character is lexicographically larger
2. i < lastIndex[st.peek()] - We'll see the previous character again later
3. !seen[curindex] - Current character hasn't been added yet

Step-by-Step Example

Let's trace through s = "bcabc":

lastIndex array: [4, 3, 2, -, -, -, ...] (a=4, b=3, c=2)

At i=2 (char 'a'):

• 'c' > 'a' and 2 < lastIndex['c']=2 ❌ (can't pop c, no more c's)
• Wait, let me recalculate: lastIndex['c'] = 4 (last occurrence of 'c')
• 'c' > 'a' and 2 < 4 ✓ (pop c)
• 'b' > 'a' and 2 < 3 ✓ (pop b)

Why This Works

Greedy Choice: At each position, we want the lexicographically smallest character possible. If we encounter a smaller character and can safely remove larger characters from our result (because they appear later), we should do so.

Stack Property: The stack maintains characters in increasing lexicographical order, ensuring the final result is optimal.

Safety Check: i < lastIndex[st.peek()] ensures we only remove characters that we'll encounter again.

Key Insights

1. Monotonic Stack: Maintains increasing order for lexicographically smallest result
2. Seen Array: Prevents processing the same character multiple times
3. Last Index: Enables safe removal of characters that appear later
4. Greedy Strategy: Always choose the smallest possible character at each step

Complexity Analysis

• Time: O(n) - each character is pushed/popped at most once
• Space: O(1) - fixed size arrays and stack of at most 26 characters

Full Solution(Java)

class Solution {
    public String removeDuplicateLetters(String s) {
        //delete the last index for each duplicated char
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i++){
            lastIndex[s.charAt(i) - 'a'] = i; // track the lastIndex of character presence
        }

        boolean[] seen = new boolean[26]; // keep track seen
        Stack<Integer> st = new Stack();

        for (int i=0; i<s.length(); i++) {
            int curindex = s.charAt(i) - 'a';

            if (seen[curindex]) continue; // if seen, pick another char
            while (!st.isEmpty() && st.peek()> curindex && i<lastIndex[st.peek()]) {
                seen[st.pop()] = false;
            }
            st.push(curindex);
            seen[curindex] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!st.isEmpty()) {
            sb.append((char) (st.pop() + 'a'));
        }
        return sb.reverse().toString();
    }
}

This solution elegantly combines greedy strategy with stack-based optimization to achieve the lexicographically smallest unique character string.