316. Remove Duplicate Letters

Description

The task is to remove duplicate letters from a string so that every letter appears once and only once. The result should also be the smallest in lexicographical order among all possible results. You are required to maintain the relative order of the original characters.

Intuition

To achieve the desired output, we need to ensure that each letter appears only once and that the resulting string is the smallest possible lexicographically. A stack-based approach works well in this situation because it allows us to make decisions about which characters to keep in a lexicographically sorted order while ensuring that we remove duplicates.

Approach

1. Stack & Seen Set: - Use a stack to build the resulting string. - A set (seen) is used to track characters already in the stack.
2. Iterate through the string: - For each character in the string: - If it’s not already in the seen set: - While the stack is not empty, and the top of the stack is greater than the current character, and the character at the top appears later in the string, remove the top of the stack. - Add the current character to the stack and mark it as seen.
3. Edge case: - If the string has repeated characters, remove them as needed by ensuring that duplicates are not re-added to the stack.
4. Build the result: - Once the stack has processed all characters, convert it to a string by concatenating the elements.

Complexity

Time Complexity:

• The time complexity is (O(n)), where (n) is the length of the string. Each character is pushed and popped from the stack at most once, and the index lookup takes constant time due to the use of a dictionary or map.

Space Complexity:

• The space complexity is (O(n)), where (n) is the number of unique characters in the string, due to the use of a stack and a set to track seen characters.

Code

C++

class Solution {
public:
    string removeDuplicateLetters(string s) {
        stack st;
        unordered_set seen;
        unordered_map last_occurrence;

        for (int i = 0; i < s.size(); i++) {
            last_occurrence[s[i]] = i;
        }

        for (int i = 0; i < s.size(); i++) {
            char ch = s[i];
            if (seen.find(ch) == seen.end()) {
                while (!st.empty() && st.top() > ch && last_occurrence[st.top()] > i) {
                    seen.erase(st.top());
                    st.pop();
                }
                st.push(ch);
                seen.insert(ch);
            }
        }

        string result = "";
        while (!st.empty()) {
            result = st.top() + result;
            st.pop();
        }

        return result;
    }
};

Python

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        seen = set()
        last_occurrence = {char: i for i, char in enumerate(s)}

        for i, char in enumerate(s):
            if char not in seen:
                while stack and stack[-1] > char and last_occurrence[stack[-1]] > i:
                    seen.remove(stack.pop())
                stack.append(char)
                seen.add(char)

        return ''.join(stack)

Java

class Solution {
    public String removeDuplicateLetters(String s) {
        Stack stack = new Stack<>();
        Set seen = new HashSet<>();
        Map lastOccurrence = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            lastOccurrence.put(s.charAt(i), i);
        }

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!seen.contains(ch)) {
                while (!stack.isEmpty() && stack.peek() > ch && lastOccurrence.get(stack.peek()) > i) {
                    seen.remove(stack.pop());
                }
                stack.push(ch);
                seen.add(ch);
            }
        }

        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.insert(0, stack.pop());
        }

        return result.toString();
    }
}

JavaScript

var removeDuplicateLetters = function (s) {

    const stack = [];
    const seen = new Set();

    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        if (!seen.has(char)) {
            while (
                stack.length > 0 &&
                stack[stack.length - 1] > char &&
                s.indexOf(stack[stack.length - 1], i) > i
            ) {
                seen.delete(stack.pop());
            }
            seen.add(char);
            stack.push(char);
        }
    }
    return stack.join('');
};