LeetCode [1209] Remove All Adjacent Duplicates in String II

 1209. Remove All Adjacent Duplicates in String II

Medium

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public String removeDuplicates(String s, int k) { Stack<int[]> stack = new Stack<>();//char-'a', cnt for(char c : s.toCharArray()){ if(stack.isEmpty()){ stack.push(new int[]{c-'a', 1}); }else{ int[] t = stack.peek(); char cLast = (char)(t[0]+'a'); int cnt = t[1]; if(cLast!=c){ stack.push(new int[]{c-'a', 1}); }else{ if(cnt+1==k){ stack.pop(); }else{ stack.peek()[1]++; } } } } StringBuilder sb = new StringBuilder(); while(!stack.isEmpty()){ int[] t = stack.pop(); char ch = (char)(t[0]+'a'); int cnt = t[1]; for(int i=0; i<cnt; ++i) sb.append(ch); } sb.reverse(); return sb.toString(); } }