1209. Remove All Adjacent Duplicates in String II

Problem

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.

Problem Summary

Given a string s, a "k-fold duplicate removal operation" chooses k adjacent and equal letters from s and deletes them, causing the left and right sides of the deleted string to concatenate together. You need to repeatedly perform this deletion operation on s an unlimited number of times until it can no longer continue. After all deletion operations have been performed, return the final resulting string. The answer to this problem is guaranteed to be unique.

Solution Approach

• Brute force solution. Every time a character is added, scan backward k positions to determine whether there are k consecutive identical characters. After eliminating k identical characters, the newly formed string may again produce k identical characters, (similar to a match-and-clear game, where k identical characters are "eliminated" when they meet), so elimination must continue. In the worst case, the string must be scanned again. Time complexity is O(n^2), space complexity is O(n).
• The inefficiency of the brute force solution lies in repeatedly counting character frequencies. It would be better if the frequency of each character were counted only once. Following this idea, use a stack, where each stack element stores 2 values: one is the character, and the other is the corresponding frequency of that character. With the frequency information of the stack-top character, there is no need to repeatedly scan backward. As long as the frequency of the stack-top character reaches k, pop that character. Repeat this process, and the remaining string at the end is the answer. Time complexity is O(n), space complexity is O(n).

Code

package leetcode

// Solution one stack
func removeDuplicates(s string, k int) string {
	stack, arr := [][2]int{}, []byte{}
	for _, c := range s {
		i := int(c - 'a')
		if len(stack) > 0 && stack[len(stack)-1][0] == i {
			stack[len(stack)-1][1]++
			if stack[len(stack)-1][1] == k {
				stack = stack[:len(stack)-1]
			}
		} else {
			stack = append(stack, [2]int{i, 1})
		}
	}
	for _, pair := range stack {
		c := byte(pair[0] + 'a')
		for i := 0; i < pair[1]; i++ {
			arr = append(arr, c)
		}
	}
	return string(arr)
}

// Solution two brute force
func removeDuplicates1(s string, k int) string {
	arr, count, tmp := []rune{}, 0, '#'
	for _, v := range s {
		arr = append(arr, v)
		for len(arr) > 0 {
			count = 0
			tmp = arr[len(arr)-1]
			for i := len(arr) - 1; i >= 0; i-- {
				if arr[i] != tmp {
					break
				}
				count++
			}
			if count == k {
				arr = arr[:len(arr)-k]
			} else {
				break
			}
		}
	}
	return string(arr)
}