🙃1209 remove all adjacent duplicates in string

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

class Solution {
    private class Pair{
        char ch;
        int count;
        public Pair(char ch) {
            this.ch = ch;
            count = 1;
        }
    }
    int length;
    public String removeDuplicates(String s, int k) {
        length = s.length();
        char[] input = s.toCharArray();
        int times = k;
        while (times > 0 && dedup(input, k)) {
            times--;
        }
        return new String(input, 0, length);
    }
    private boolean dedup(char[] input, int k) {
        Deque<Pair> deque = new ArrayDeque<>();
        for (int i = 0; i < length; i++) {
            char ch = input[i];
            if (deque.isEmpty()){
                deque.offerFirst(new Pair(ch));
            } else {
                Pair pair = deque.peekFirst();
                if (pair.ch == ch) {
                    pair.count++;
                    if (pair.count == k) {
                        deque.pollFirst();
                    }
                } else {
                    deque.offerFirst(new Pair(ch));
                }
            }
        }
        int newLen = 0;
        while (!deque.isEmpty()) {
            Pair pair = deque.pollLast();
            for (int i = 0; i < pair.count; i++) {
                input[newLen++] = pair.ch;
            }
        }
        boolean deduped = newLen < length;
        length = newLen;
        return deduped;
    }
}

因为需要知道到底有多少个重复的所以用了deque来记录之前的，同时注意题的要求其实是如果有n>k个重复的，只去掉其中的k个就行。注意这道题不用in place，完全可以用deque记下这轮dedup之后的数组然后再还原出来。

update: 一个月之后做这道题还是觉得很恶心，题意就是他娘的傻逼，不仅要求你一次remove k个连续的，而且removal也只能做k次，建议发明这道题的人去死