Course4all
Join us on telegram
Home/dsa/Stack/Remove Duplicate Letters

Remove Duplicate Letters

Master this topic with zero to advance depth.

Remove Duplicate Letters

Remove duplicate letters from string s so that every letter appears once. The result must be the smallest in lexicographical order among all possible results.

Visual Representation

s = "bcabc" Counts: {b:2, c:2, a:1} 1. 'b': Push. Stack: [b]. Counts: {b:1, c:2, a:1} 2. 'c': Push. Stack: [b, c]. Counts: {b:1, c:1, a:1} 3. 'a': - 'c' > 'a' and c's count > 0. Pop c. - 'b' > 'a' and b's count > 0. Pop b. - Push 'a'. Stack: [a]. Counts: {b:1, c:1, a:0} 4. 'b': Push. Stack: [a, b]. Counts: {b:0, c:1, a:0} 5. 'c': Push. Stack: [a, b, c]. Counts: {b:0, c:0, a:0} Result: "abc"
Medium

Examples

Input: s = "bcabc"
Output: "abc"
Approach 1

Level I: Generate All Subsequences, Filter, Then Sort

Intuition

Generate all unique subsequences of the string that contain each character exactly once (using a set of frequency tracking). Filter to keep valid ones and return the lexicographically smallest. This is exponential and only feasible for tiny inputs.

⏱ O(2^N * N) — exponential in string length.💾 O(2^N) for storing all unique subsequences.
java
import java.util.*;

public class Main {
    static Set<String> seen = new HashSet<>();
    
    public static String removeDuplicateLetters(String s) {
        Set<Character> chars = new HashSet<>();
        for (char c : s.toCharArray()) chars.add(c);
        int n = chars.size();
        List<String> valid = new ArrayList<>();
        generateSubseqs(s, 0, "", new int[26], valid, n, new int[26]);
        Collections.sort(valid);
        return valid.get(0);
    }
    
    static void generateSubseqs(String s, int i, String cur, int[] used, List<String> valid, int targetLen, int[] freq) {
        if (cur.length() == targetLen) { valid.add(cur); return; }
        if (i == s.length()) return;
        char c = s.charAt(i);
        if (used[c - 'a'] == 0) {
            used[c - 'a'] = 1;
            generateSubseqs(s, i + 1, cur + c, used, valid, targetLen, freq);
            used[c - 'a'] = 0;
        }
        generateSubseqs(s, i + 1, cur, used, valid, targetLen, freq);
    }

    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters("bcabc")); // abc
    }
}
Approach 2

Level III: Optimal (Greedy Monotonic Stack)

Intuition

Maintain a stack of characters that represents the current smallest lexicographical result. Use a frequency map to know if a character will appear later. If the current character is smaller than the stack top and the stack top appears again later, pop the stack top. Use a seen set to skip characters already in the result.

⏱ O(N)💾 O(1) - alphabet size

Detailed Dry Run

CharActionStackSeenCount Left
'b'Push[b]{b}b:1
'c'Push[b, c]{b, c}c:1
'a'Pop b, c; Push a[a]{a}a:0
'b'Push[a, b]{a, b}b:0
java
import java.util.*;

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
        boolean[] seen = new boolean[26];
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen[c - 'a']) continue;
            while (!st.isEmpty() && st.peek() > c && last[st.peek() - 'a'] > i) {
                seen[st.pop() - 'a'] = false;
            }
            st.push(c);
            seen[c - 'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (char c : st) sb.append(c);
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.removeDuplicateLetters("bcabc")); // "abc"
    }
}

⚠️ Common Pitfalls & Tips

You can only pop a character if you know it appears later in the string. Character counts or last-occurrence indices are necessary.

← Previous QuestionDecode String
Next Question →Basic Calculator