Remove Duplicate Letters (M)
題目
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.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
Example 1:
Input: s = "bcabc"
Output: "abc"
Example 2:
Input: s = "cbacdcbc"
Output: "acdb"
Constraints:
1 <= s.length <= 10^4sconsists of lowercase English letters.
題意
刪去字串里重復的字母，使剩下的字母都只出現一次且得到的字串在所有可能結果中字典序最小，
思路
先遍歷一遍統計所有字母出現的次數，
再次遍歷字串，如果當前字符c已經安排在結果字串s中，則跳過；若還未安排，將c與s中最后一個字符c'進行比較，如果c<c'且c'在之后還會出現，則洗掉c'，重復該操作直到末尾所有滿足的c'都被洗掉，最后將c加到s的末尾，
代碼實作
Java
class Solution {
public String removeDuplicateLetters(String s) {
Deque<Character> deque = new ArrayDeque<>();
int[] count = new int[26];
boolean[] used = new boolean[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
for (char c : s.toCharArray()) {
if (!used[c - 'a']) {
while (!deque.isEmpty() && c < deque.peekLast() && count[deque.peekLast() - 'a'] > 0) {
used[deque.peekLast() - 'a'] = false;
deque.pollLast();
}
deque.offer(c);
used[c - 'a'] = true;
}
count[c - 'a']--;
}
StringBuilder sb = new StringBuilder();
while (!deque.isEmpty()) {
sb.append(deque.poll());
}
return sb.toString();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/168059.html
標籤：其他
上一篇：程式猿DD 是誰？
下一篇：字串的排列