Remove All Adjacent Duplicates in String II

Head on over here to try to the problem for yourself.

The problem requires a stack based solution.

Algorithm

The goal is the find the shortest string possible by removing `k` duplicated adjacent characters. A simple problem case is illustrated:

``````k = 2
s = "abbac"
the result must be c.

Iteration 1: remove bb => "aac"
Iteration 2: remove aa => "c"
``````

The hint points out that instead of maintaining the character count outside the stack, just pass in an object that stores the counter. I have passed an object and an array to arrive at two similar solutions, one with less memory overhead, and the latter with better performance.

Code

Object - Pair
``````public class Pair {
char c;
int n;

public Pair(char curr) {
c = curr;
n = 1;
}

public void increment() {
n++;
}

public String stringRep() {
return Character.toString(c).repeat(n);
}
}
public String removeDuplicates(String s, int k) {
Stack<Pair> st = new Stack();
char curr;
for(int i = 0; i < s.length(); i++) {

curr = s.charAt(i);
if(st.empty() || st.peek().c != curr)
st.push(new Pair(curr));
else st.peek().increment();

if(st.peek().n == k) st.pop();
}

StringBuilder result = new StringBuilder();
for(Pair p : st) {
result.append(p.stringRep());
}
return result.toString();
}
``````
Object - array
``````public String removeDuplicates(String s, int k) {
Stack<int[] > st = new Stack();
char curr;

for(int i = 0; i < s.length(); i++) {
curr = s.charAt(i);

if(st.empty() || st.peek()[0] != curr)
st.push(new int[] {curr, 1});
else st.peek()[1]++;

if(st.peek()[1] == k) st.pop();
}

StringBuilder result = new StringBuilder();
for(int[] a : st) {
while(a[1]-- > 0)
result.append((char)a[0]);
}
return result.toString();
}
``````