316. Remove Duplicate Letters

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 <= 104
• s consists of lowercase English letters.

---

Solutions

Solution 1

Intuition

Greedy, stack + frequent map + add flags

Code

class Solution {

    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        int[] freq = new int[26];
        boolean[] added = new boolean[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            freq[c - 'a']--;
            if (added[c - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && stack.peek() > c && freq[stack.peek() - 'a'] > 0) {
                added[stack.pop() - 'a'] = false;
            }
            stack.push(c);
            added[c - 'a'] = true;
        }
        StringBuilder ans = new StringBuilder();
        for (char c : stack) {
            ans.append(c);
        }
        return ans.toString();
    }
}

Complexity

• Time: O(n)
• Space: O(n)