LeetCode: Remove All Adjacent Duplicates in String II Posted on August 5, 2019July 26, 2020 by braindenny Remove All Adjacent Duplicates in String II Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups LeetCode: Remove All Adjacent Duplicates In String Tag: #stack 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. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: // https://code.dennyzhang.com/remove-all-adjacent-duplicates-in-string-ii // Basic Ideas: stack // // Complexity: Time O(n), Space O(n) type MyNode struct { ch byte cnt int } func removeDuplicates(s string, k int) string { stack := []MyNode{} for i, _ := range s { ch := s[i] if len(stack)>0 && stack[len(stack)-1].ch == ch { stack[len(stack)-1].cnt += 1 if stack[len(stack)-1].cnt == k { stack = stack[0:len(stack)-1] } } else { stack = append(stack, MyNode{ch:ch, cnt:1}) } } l := []byte{} for _, node := range stack { for i:=0; i<node.cnt; i++ { l = append(l, node.ch) } } return string(l) } Post Views: 0