Remove All Adjacent Duplicates in String II
给一个string, 只移除k次重复的substring.
这个题因为要多次移除, 还有merge的可能, 所以要用stack存一下前序, 我是用Pair先预处理了一下string, 把string换成词频格式, 然后再用stack. 其实也可以不用pair, 直接算.
class Solution {
class Pair{
char a;
int b;
Pair(char a, int b){
this.a = a;
this.b = b;
}
public String toString(){
return this.a +"|" + this.b;
}
}
public String removeDuplicates(String s, int k) {
List<Pair> pairs = new LinkedList<>();
for(int i = 0; i < s.length(); i++) {
if(pairs.isEmpty() || pairs.get(pairs.size() - 1).a != s.charAt(i)){
Pair p = new Pair(s.charAt(i), 1);
pairs.add(p);
} else if(pairs.get(pairs.size() - 1).a == s.charAt(i)){
Pair p = new Pair(pairs.get(pairs.size() - 1).a, pairs.get(pairs.size() - 1).b + 1);
pairs.remove(pairs.size() - 1);
pairs.add(p);
}
}
Stack<Pair> st = new Stack<>();
for(int i = 0; i < pairs.size(); i++){
if(st.isEmpty()){
st.push(pairs.get(i));
}
else if(st.peek().a == pairs.get(i).a){
Pair p = st.pop();
p.b += pairs.get(i).b;
st.push(p);
}else{
st.push(pairs.get(i));
}
if(!st.isEmpty()){
Pair p = st.pop();
if(p.b % k != 0){
p.b = p.b % k;
st.push(p);
}
}
}
StringBuilder sb = new StringBuilder();
while(!st.isEmpty()){
Pair p = st.pop();
for(int i = 0; i < p.b; i++) {
sb.insert(0, p.a);
}
}
return sb.toString();
}
}