1209. Remove All Adjacent Duplicates in String II

Back to Homepage   |     Back to Code List


class Solution {
    class Node {
        char ch;
        int times;
        public Node(char c, int t) {
            ch = c;
            times = t;
        }
    }

    public String removeDuplicates(String s, int k) {
        int n = s.length();
        if (n < k) return s;
        Deque<Node> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (stack.isEmpty() || c != stack.peek().ch) {
                stack.push(new Node(c, 1));
            } else {
                int repeated = stack.peek().times;

                if (k == repeated + 1) {
                    stack.pop();
                } else {
                    stack.peek().times++;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Node node : stack) {
            int repeated = node.times;
            for (int i = 0; i < repeated; i++) {
                sb.append(node.ch);
            }
        }

        return sb.reverse().toString();
    }
}