leetcode 1209. Remove All Adjacent Duplicates in String II

Seawolf

1. 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.
   
2. 
   
3. We repeatedly make k duplicate removals on s until we no longer can.
   
4. 
   
5. Return the final string after all such duplicate removals have been made.
   
6. 
   
7. It is guaranteed that the answer is unique.
   
8. 
   
9. 
   
10. 
    
11. Example 1:
    
12. 
    
13. Input: s = "abcd", k = 2
    
14. Output: "abcd"
    
15. Explanation: There's nothing to delete.
    
16. Example 2:
    
17. 
    
18. Input: s = "deeedbbcccbdaa", k = 3
    
19. Output: "aa"
    
20. Explanation:
    
21. First delete "eee" and "ccc", get "ddbbbdaa"
    
22. Then delete "bbb", get "dddaa"
    
23. Finally delete "ddd", get "aa"
    
24. Example 3:
    
25. 
    
26. Input: s = "pbbcggttciiippooaais", k = 2
    
27. Output: "ps"
    
28. 
    
29. 
    
30. Constraints:
    
31. 
    
32. 1 <= s.length <= 10^5
    
33. 2 <= k <= 10^4
    
34. s only contains lower case English letters.

复制代码

1. class Solution {
   
2.     public String removeDuplicates(String s, int k) {
   
3.         Stack <Character> stack_c = new Stack<>();
   
4.         Stack <Integer> stack_n = new Stack<>();
   
5.         
   
6.         for(int i = 0; i < s.length(); i++){
   
7.             
   
8.             if(!stack_c.isEmpty() && stack_c.peek() == s.charAt(i)){
   
9.                
   
10.                 stack_n.push(stack_n.peek()+1);
    
11.             }else{
    
12.                
    
13.                 stack_n.push(1);
    
14.             }
    
15.             
    
16.             stack_c.push(s.charAt(i));
    
17.             
    
18.             if(stack_n.peek() == k){
    
19.                
    
20.                 for(int j = 0; j< k ; j++){
    
21.                     
    
22.                     stack_n.pop();
    
23.                     stack_c.pop();
    
24.                 }
    
25.             }
    
26.         }
    
27.         
    
28.         StringBuilder ret = new StringBuilder();
    
29.         
    
30.         while(!stack_c.isEmpty()){
    
31.             
    
32.             ret.append(stack_c.pop());
    
33.         }
    
34.         
    
35.         return ret.reverse().toString();
    
36.     }
    
37. }

复制代码