DEV Community

Kardel Chen
Kardel Chen

Posted on

Leetcode 1209 Remove All Adjacent Duplicates in String II

import java.util.Stack;

class Solution {
    class Wrapper{
        // wrapper for counting adjacent duplicates in String
        //c -> character
        char c;
        //n -> count number
        int n;
        Wrapper(char c, int n){
            this.c = c;
            this.n = n;
        }

        @Override
        public String toString() {
            return "Wrapper{" +
                    "c=" + c +
                    ", n=" + n +
                    '}';
        }
    }
    public String removeDuplicates(String s, int k) {
        Stack<Wrapper> stack = new Stack<>();
        int i = 0;
        //use sliding window O(n) to count duplicate adjacent elements
        while(i < s.length()){
            char c = s.charAt(i);
            int j = i+1;
            while(j < s.length() && s.charAt(j)==c){
                j++;
            }
            int left = (j-i);// duplicate numbers
            // find previous  Wrappers
            while(!stack.isEmpty() && stack.peek().c == c){
                Wrapper pop = stack.pop();
                left += pop.n;
            }
            left = left % k;
            if(left != 0) {
                stack.push(new Wrapper(c, left));
            }
            // update i
            i = j;
        }
        StringBuilder sb = new StringBuilder();
        for (Wrapper wrapper : stack) {
            sb.append(String.valueOf(wrapper.c).repeat(Math.max(0, wrapper.n)));
        }

        return sb.toString();
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)