316. Remove Duplicate Letters

Problem 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

Python Solution

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # Count frequency of each character
        last_occurrence = {c: i for i, c in enumerate(s)}
        
        # Keep track of characters in result
        seen = set()
        stack = []
        
        for i, c in enumerate(s):
            if c not in seen:
                # Pop characters that are greater and can be added later
                while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
                    seen.remove(stack.pop())
                stack.append(c)
                seen.add(c)
        
        return ''.join(stack)

Java Solution

class Solution {
    public String removeDuplicateLetters(String s) {
        // Count frequency of each character
        int[] lastOccurrence = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence[s.charAt(i) - 'a'] = i;
        }
        
        // Keep track of characters in result
        boolean[] seen = new boolean[26];
        Stack stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!seen[c - 'a']) {
                // Pop characters that are greater and can be added later
                while (!stack.isEmpty() && c < stack.peek() && 
                       i < lastOccurrence[stack.peek() - 'a']) {
                    seen[stack.pop() - 'a'] = false;
                }
                stack.push(c);
                seen[c - 'a'] = true;
            }
        }
        
        // Build result string
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }
        return result.toString();
    }
}

C++ Solution

class Solution {
public:
    string removeDuplicateLetters(string s) {
        // Count frequency of each character
        vector lastOccurrence(26, 0);
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence[s[i] - 'a'] = i;
        }
        
        // Keep track of characters in result
        vector seen(26, false);
        stack st;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            if (!seen[c - 'a']) {
                // Pop characters that are greater and can be added later
                while (!st.empty() && c < st.top() && 
                       i < lastOccurrence[st.top() - 'a']) {
                    seen[st.top() - 'a'] = false;
                    st.pop();
                }
                st.push(c);
                seen[c - 'a'] = true;
            }
        }
        
        // Build result string
        string result = "";
        while (!st.empty()) {
            result = st.top() + result;
            st.pop();
        }
        return result;
    }
};

JavaScript Solution

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
    // Count frequency of each character
    const lastOccurrence = {};
    for (let i = 0; i < s.length; i++) {
        lastOccurrence[s[i]] = i;
    }
    
    // Keep track of characters in result
    const seen = new Set();
    const stack = [];
    
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (!seen.has(c)) {
            // Pop characters that are greater and can be added later
            while (stack.length > 0 && c < stack[stack.length - 1] && 
                   i < lastOccurrence[stack[stack.length - 1]]) {
                seen.delete(stack.pop());
            }
            stack.push(c);
            seen.add(c);
        }
    }
    
    return stack.join('');
};

C# Solution

public class Solution {
    public string RemoveDuplicateLetters(string s) {
        // Count frequency of each character
        int[] lastOccurrence = new int[26];
        for (int i = 0; i < s.Length; i++) {
            lastOccurrence[s[i] - 'a'] = i;
        }
        
        // Keep track of characters in result
        bool[] seen = new bool[26];
        Stack stack = new Stack();
        
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (!seen[c - 'a']) {
                // Pop characters that are greater and can be added later
                while (stack.Count > 0 && c < stack.Peek() && 
                       i < lastOccurrence[stack.Peek() - 'a']) {
                    seen[stack.Pop() - 'a'] = false;
                }
                stack.Push(c);
                seen[c - 'a'] = true;
            }
        }
        
        // Build result string
        char[] result = stack.ToArray();
        Array.Reverse(result);
        return new string(result);
    }
}