描述:
给定一个字符串S,选择至少出现2次的任何字符并删除其中任何一个,重复操作,直到没有重复的字符串,并得到按照字符排序的最大字符串
例如:
S = “aabcb”,返回结果为“acb” (分别删除了第一个a和b)
public static String removeDuplicateLetters(String s) {
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
Stack<Character> st = new Stack<>();
// 记录stack里面有没有该字符
HashMap<Character, Boolean> existHashMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!existHashMap.containsKey(ch) || !existHashMap.get(ch)) {
// map记录 还剩下多少个该字符串
// 字符串后面还有stack顶的字符,并且比stack顶的字符大,才能把栈顶的字符pop出来,
while (st.size() > 0 && map.containsKey(st.peek()) && st.peek() < ch ) {
existHashMap.put( st.pop(), false);
}
st.push(ch);
existHashMap.put(ch, true);
}
map.put(ch, map.get(ch) - 1);
if (map.get(ch) == 0) {
map.remove(ch);
}
}
StringBuilder ans = new StringBuilder();
while (st.size() > 0) {
ans.insert(0, st.pop());
}
return ans.toString();
}
网友评论