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-
sconsists 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)
Top comments (0)