316. Remove Duplicate Letters

Problem Statement

Pattern:

---

Solution

public String removeDuplicateLetters(String s) {
	// find smallest char
	int[] lastIndex = new int[26];
	char[] chars = s.toCharArray();
	int si = 0, n = s.length();
	Deque<Character> stack = new LinkedList<>();
	HashSet<Character> stackSet = new HashSet<>();
 
	// get last indices
	for (int i = 0; i < chars.length; i++) lastIndex[chars[i] - 'a'] = i;
 
	for (int i = 0; i < n; i++) {
		char ch = chars[i];
		if (!stackSet.contains(ch)) {
			while (!stack.isEmpty() && ch < stack.peek() && lastIndex[stack.peek() - 'a'] > i ) stackSet.remove(stack.pop());
			stack.push(ch);
			stackSet.add(ch);
		}
	}
 
	// convert to string
	StringBuilder sb = new StringBuilder();
	for (char ch : stack) sb.append(ch);
	return sb.reverse().toString();
}

TC : $O(n)$ SC : $O(n)$

Notes