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();
}