Remove Duplicate Letters - Medium - L - Star
Published:
Question
- https://leetcode.com/problems/remove-duplicate-letters/
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.
Approach
- Stacks, vis and last Index
Solution
class Solution {
public String removeDuplicateLetters(String s) {
int[] lastIndex = new int[26];
for (int i = 0; i < s.length(); i++)
lastIndex[s.charAt(i) - 'a'] = i; // track the lastIndex of character presence
boolean[] seen = new boolean[26]; // keep track seen
Stack<Integer> st = new Stack();
for (int i = 0; i < s.length(); i++) {
int c = s.charAt(i) - 'a';
if (seen[c]) continue; // if seen continue as we need to pick one char only
while (!st.isEmpty() && st.peek() > c && i < lastIndex[st.peek()])
seen[st.pop()] = false; // pop out and mark unseen
st.push(c); // add into stack
seen[c] = true; // mark seen
}
StringBuilder sb = new StringBuilder();
while (!st.isEmpty())
sb.append((char) (st.pop() + 'a'));
return sb.reverse().toString();
}
}