问题描述
You are given a string s and an integer k, 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.
问题分析
这个问题容易让人联想到俄罗斯方块，拼好一层消掉；类似的，这里我们采用stack来解决这个问题
相比较于普通的stack，这次我们需要对元素类型做一下自定义:
type item struct {
val byte // 字符
consecutiveCount int // 该字符连续出现的次数
}
每次往stack里Push时，进行如下判断:
- 如果当前栈顶元素和待push的元素相同，则不必push，只是连续出现次数+1；
- 如果不同，直接push; 同时连续出现次数初始化为1
- 判断栈顶字符的连续出现次数是否等于指定的k，如果等于，pop即可
全部字符处理完后，stack中剩下的即为所求。全部pop出来，逆序输出即可。
示例代码–stack版
// stack
func removeDuplicates(s string, k int) string {
stack := stack{}
for i := 0; i < len(s); i++ {
stack.Push(s[i], k)
}
ans := []byte{}
for {
item := stack.Pop()
if item == nil {
break
}
ans = append([]byte{item.val}, ans...)
}
return string(ans)
}
type stack struct {
list []*item
}
type item struct {
val byte
consecutiveCount int
}
func (s *stack) Pop() *item {
if len(s.list) == 0 {
return nil
}
ans := s.list[len(s.list)-1]
s.list = s.list[:len(s.list)-1]
return ans
}
func (s *stack) Push(v byte, k int) {
item := item{
val: v,
consecutiveCount: 1,
}
if len(s.list) > 0 {
last := s.list[len(s.list)-1]
if last.val == v {
// pop
if last.consecutiveCount == k-1 {
s.list = s.list[:len(s.list)-k+1]
return
}
item.consecutiveCount = last.consecutiveCount + 1
}
}
s.list = append(s.list, &item)
}
示例代码–2 pointers版
stack版的解法提交AC后，在评论区发现还有另外一种解法，利用字符数组+双指针去模拟刚才stack的行为，具体逻辑如下：
- 初始化2个指针i，j； i表示栈顶； j表示当前遍历到的字符
- 定义一个计数map，记为m
- 首先，rs[i] = rs[j]； 表示将当前遍历的字符压入栈
- 如果 rs[i-1]与rs[j]相同，此时 m[i]计数在m[i-1]基础上+1; 否则初始化为1即可
- 如果 m[i] == k，说明栈顶k个元素相同，此时直接将i回退k个位置
以上步骤执行完，返回字符数组的子数组 rs[0:i+1]， 转为字符串即为所求
// 2 pointers
func removeDuplicatesV2(s string, k int) string {
rs := []rune(s)
i, lens := -1, len(s)
m := make(map[int]int)
for j := 0; j < lens; j++ {
i++
rs[i] = rs[j]
if i > 0 && rs[i-1] == rs[j] {
m[i] = m[i-1] + 1
} else {
m[i] = 1
}
if m[i] == k {
i -= k
}
}
return string(rs[0 : i+1])
}