import java.util.Stack;
class Solution {
class Wrapper{
// wrapper for counting adjacent duplicates in String
//c -> character
char c;
//n -> count number
int n;
Wrapper(char c, int n){
this.c = c;
this.n = n;
}
@Override
public String toString() {
return "Wrapper{" +
"c=" + c +
", n=" + n +
'}';
}
}
public String removeDuplicates(String s, int k) {
Stack<Wrapper> stack = new Stack<>();
int i = 0;
//use sliding window O(n) to count duplicate adjacent elements
while(i < s.length()){
char c = s.charAt(i);
int j = i+1;
while(j < s.length() && s.charAt(j)==c){
j++;
}
int left = (j-i);// duplicate numbers
// find previous Wrappers
while(!stack.isEmpty() && stack.peek().c == c){
Wrapper pop = stack.pop();
left += pop.n;
}
left = left % k;
if(left != 0) {
stack.push(new Wrapper(c, left));
}
// update i
i = j;
}
StringBuilder sb = new StringBuilder();
for (Wrapper wrapper : stack) {
sb.append(String.valueOf(wrapper.c).repeat(Math.max(0, wrapper.n)));
}
return sb.toString();
}
}
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)