0316. Remove Duplicate Letters
https://leetcode.com/problems/remove-duplicate-letters
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
s
consists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
ac
class Solution {
public String removeDuplicateLetters(String s) {
// edge cases
if (s.length() <= 1) return s;
int n = s.length();
int[] cnts = new int[26];
for (char c : s.toCharArray()) {
cnts[c - 'a']++;
}
boolean[] onStack = new boolean[26];
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
cnts[c - 'a']--;
if (onStack[c - 'a']) {
continue; // skip
}
while (!stack.isEmpty() && c < stack.peek() && cnts[stack.peek() - 'a'] > 0) {
onStack[stack.pop() - 'a'] = false;
}
stack.push(c);
onStack[c - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
/*
stack, walk string, if meet smaller char and old char has more later, pop old.
*/
Last updated
Was this helpful?