05 August 2008
删除k倍相邻的字符，删除后再相邻也要删除，循环往复操作 - 栈，当前字符与前一个不同时，往栈中压入 1，否则栈顶元素加 1，时空复杂度均为O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String removeDuplicates(String s, int k) {
StringBuilder sb = new StringBuilder(s);
Stack<Integer> counts = new Stack<>();
for (int i = 0; i < sb.length(); ++i) {
if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) {
counts.push(1);
} else {
int incremented = counts.pop() + 1;
if (incremented == k) {
sb.delete(i - k + 1, i + 1);
i = i - k;
} else {
counts.push(incremented);
}
}
}
return sb.toString();
}