LeetCode-in-Java

316. Remove Duplicate Letters

Medium

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:

Note: This question is the same as 1081.

Solution

public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] charCount = new int[26];
        boolean[] charAdded = new boolean[26];
        // Build the char count array
        for (char c : s.toCharArray()) {
            charCount[c - 'a'] += 1;
        }
        StringBuilder sb = new StringBuilder();
        // i = index of the input string
        // j = index of the output stringBuilder
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            // If the curr char is NOT already added in the final string
            if (!charAdded[curr - 'a']) {
                // If the prev char in final string is lexicographically greater than curr char of
                // input string
                // And there are more characters in charCount array then we can remove this prev
                // char from final string
                // Do this check iteratively until all characters are removed from the final string
                // or prev char < curr char
                while (j > 0 && sb.charAt(j - 1) > curr && charCount[sb.charAt(j - 1) - 'a'] > 0) {
                    charAdded[sb.charAt(j - 1) - 'a'] = false;
                    sb.deleteCharAt(j - 1);
                    j--;
                }
                // Add the curr char in final string and mark that character as added in the string
                sb.append(curr);
                charAdded[curr - 'a'] = true;
                j++;
            }
            // Reduce the count of the current character from the charCount array
            charCount[curr - 'a'] -= 1;
        }
        return sb.toString();
    }
}