leetcode 1209. Remove All Adjacent Duplicates in String II

Seawolf

Given a string s, 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.

 

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.
Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"
 

Constraints:

1 <= s.length <= 10^5
2 <= k <= 10^4
s only contains lower case English letters.

class Solution {
    public String removeDuplicates(String s, int k) {
        Stack <Character> stack_c = new Stack<>();
        Stack <Integer> stack_n = new Stack<>();
        
        for(int i = 0; i < s.length(); i++){
            
            if(!stack_c.isEmpty() && stack_c.peek() == s.charAt(i)){
                
                stack_n.push(stack_n.peek()+1);
            }else{
                
                stack_n.push(1);
            }
            
            stack_c.push(s.charAt(i));
            
            if(stack_n.peek() == k){
                
                for(int j = 0; j< k ; j++){
                    
                    stack_n.pop();
                    stack_c.pop();
                }
            }
        }
        
        StringBuilder ret = new StringBuilder();
        
        while(!stack_c.isEmpty()){
            
            ret.append(stack_c.pop());
        }
        
        return ret.reverse().toString();
    }
}