Last updated on January 9th, 2025 at 03:31 am

Here, we see a Remove Duplicate Letters LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Greedy, Stack

Companies

Google

Level of Question

Medium

Remove Duplicate Letters LeetCode Solution

1. Problem Statement

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”

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Monotonic Stack”. This pattern involves maintaining a stack where elements are added or removed based on a specific order (in this case, lexicographical order). The stack ensures that the resulting string is the smallest lexicographical order while maintaining the condition of removing duplicate letters.

3. Code Implementation in Different Languages

3.1 Remove Duplicate Letters C++

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> cnt(26,0)  , vis(26,0);
        string res = "";
        int n = s.size();
        for(int i = 0; i<n; ++i)
            cnt[s[i] - 'a']++;
        for(int i = 0; i<n; ++i)
        {
            cnt[s[i] - 'a']--;
            if(!vis[s[i]- 'a'])
            {
                while(res.size() > 0 && res.back() > s[i] && cnt[res.back() - 'a'] > 0)
                {
                    vis[res.back() - 'a'] = 0;
                    res.pop_back();
                }
                res += s[i];
                vis[s[i] - 'a'] = 1;
            }
        }
        return res;
    }
};

3.2 Remove Duplicate Letters Java

class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        Set<Character> seen = new HashSet<>();
        Map<Character, Integer> lastOcc = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastOcc.put(s.charAt(i), i);
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!seen.contains(c)) {
                while (!stack.isEmpty() && c < stack.peek() && i < lastOcc.get(stack.peek())) {
                    seen.remove(stack.pop());
                }
                seen.add(c);
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }
        return result.toString();
    }
}

3.3 Remove Duplicate Letters JavaScript

var removeDuplicateLetters = function(s) {
    let stack = [];
    let seen = new Set();
    let lastOcc = {};
    for (let i = 0; i < s.length; i++) {
        lastOcc[s[i]] = i;
    }
    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        if (!seen.has(c)) {
            while (stack.length && c < stack[stack.length - 1] && i < lastOcc[stack[stack.length - 1]]) {
                seen.delete(stack.pop());
            }
            seen.add(c);
            stack.push(c);
        }
    }
    return stack.join('');
}

3.4 Remove Duplicate Letters Python

class Solution(object):
    def removeDuplicateLetters(self, s):
        stack = []
        seen = set() 
        last_occ = {c: i for i, c in enumerate(s)}
        for i, c in enumerate(s):
            if c not in seen:
                while stack and c < stack[-1] and i < last_occ[stack[-1]]:
                    seen.discard(stack.pop())
                seen.add(c)
                stack.append(c)
        return ''.join(stack)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)