316. Remove Duplicate Letters

Version #2 Stack
I feel this algorithm super complicated...

1Bug ->
we should decrease counter before we are doing anything
we should continue before we pop anything


class Solution {
    public String removeDuplicateLetters(String s) {
// we are always trying to put letters with smaller lexicographical order before letters with larger lexicographical order
// e.g. {b a b} -> result is {a, b}
// We are trying our best to make a lexicographically increasing array
// if the coming letter is smaller than our tail letter, and the tail letter has another candidate with larger index,
// then we are able to remove the tail and append the coming letter
// if the coming letter is larger than our tail letter, it is guarded by current letter to be a lexicographically increasing
// array, and it will be checked by letters after itself
int[] counter = new int[26];
for (int i = 0; i < s.length(); i++) {
counter[s.charAt(i) - 'a']++;
}
// if a character has already be chosen and it is larger than current character, we don't choose it, since it is guarding
// its next character
// e.g. {b, c, a, b} -> b > a but we can't replace b(0) by b(3), since if we removed b(0), the c(1) that is guarded by b(0) will
// be exposed and increase the totally lexicographical order
boolean[] visited = new boolean[26];
Stack<Character> stack = new Stack();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
counter[curr - 'a']--;
if (visited[curr - 'a']) continue;
while (!stack.isEmpty() && curr < stack.peek() && counter[stack.peek() - 'a'] > 0) {
// we can remove these larger letters and pick them in the future
visited[stack.peek() - 'a'] = false;
stack.pop();
}
// state -> either curr > stack.peek() or we are using the last occurrence of stack.peek()
stack.push(curr);
visited[curr - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}


Version #1 Brute Force DFS [TLE]
failed at
"bxshkpdwcsjdbikywvioxrypfzfbppydfilfxxtouzzjxaymjpmdoevv"
class Solution {
    public String removeDuplicateLetters(String s) {
// key-characters, value-list of indexes of their occurrence
List<List<Integer>> map = new LinkedList<>();
for (int i = 0; i < 26; i++) map.add(new ArrayList<>());
for (int i = 0; i < s.length(); i++) {
map.get(s.charAt(i) - 'a').add(i);
}
String[] result = new String[1];
dfs(0, map, new ArrayList<>(), s, result);
return result[0];
}

// iterate through 26 characters, pick one index
private void dfs(int characterIndex, List<List<Integer>> map, List<Integer> path, String s, String[] result) {
if (characterIndex >= 26) {
List<Integer> temp = new ArrayList<>(path);
Collections.sort(temp);
StringBuilder sb = new StringBuilder();
for (int index : temp) {
sb.append(s.charAt(index));
}
String res = sb.toString();
if (result[0] == null || res.compareTo(result[0]) < 0) {
result[0] = res;
}
return;
}
if (map.get(characterIndex).size() == 0) {
dfs(characterIndex + 1, map, path, s, result);
} else {
for (int curr : map.get(characterIndex)) {
path.add(curr);
dfs(characterIndex + 1, map, path, s, result);
path.remove(path.size() - 1);
}
}
}
}