1209. Remove All Adjacent Duplicates in String II

Question

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Solution

用一个栈保存当前的字符，同时建立一个cnt[]数组记录当前字符连续出现的次数。

遍历字符串。

如果当前的字符与栈顶的字符相同时，获取数组中记录的当前连续次数lastCount并加一。
如果lastCount等于k，则匹配到了足够的字符，去掉栈顶的k - 1个元素。
否则将字符串加入栈顶，记录当前位置的出现次数lastCount。

如果当前字符与栈顶字符不同，则将字符直接加入栈顶，记录当前位置的cnt[dq.size()]为1。

最后将栈内元素倒序组成字符串。由于需要这一步操作，因此之前的栈采用双端队列实现。

Code

class Solution {
    public String removeDuplicates(String s, int k) {
        Deque<Character> dq = new LinkedList<Character>();
        int[] cnt = new int[s.length()+1];

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(i > 0 && !dq.isEmpty() && dq.peek() == c){
                int lastCount = cnt[dq.size()];
                lastCount++;
                if(lastCount == k){
                    while(lastCount != 1){
                        dq.removeFirst();
                        lastCount--;
                    }
                }
                else{
                    dq.offerFirst(c);
                    cnt[dq.size()] = lastCount;
                }
            }
            else{
                dq.offerFirst(c);
                cnt[dq.size()] = 1;
            }
        }
        
        StringBuffer sb = new StringBuffer();
        while(!dq.isEmpty()){
            sb.append(dq.removeLast());
        }
        return sb.toString();
    }
}