LeetCode 316: Remove Duplicate Letters Solution

Master LeetCode problem 316 (Remove Duplicate Letters), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

316. Remove Duplicate Letters

Medium

String Stack Greedy Monotonic Stack

Problem Explanation

Explanation

To solve this problem, we can use a stack to maintain the characters of the final result. We iterate through the input string s and for each character:

If the character is already present in the stack, we skip it.
If the character is smaller than the top of the stack and the top of the stack will occur later in the string again, we pop the top of the stack.
Finally, we push the current character onto the stack.

This way, we ensure that the result is the smallest lexicographical order and has distinct characters.

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1) since the stack will contain at most 26 characters.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 316 (Remove Duplicate Letters)?

This page provides optimized solutions for LeetCode problem 316 (Remove Duplicate Letters) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 316 (Remove Duplicate Letters)?

The time complexity for LeetCode 316 (Remove Duplicate Letters) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 316 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 316 in Java, C++, or Python.

Back to LeetCode Solutions