2 minutes
Leetcode 1209
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();
}