Description#
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 <= 1052 <= k <= 104s only contains lowercase English letters.
Solutions#
Solution 1: Stack#
We can traverse the string $s$, maintaining a stack that stores the characters and their occurrence counts. When traversing to character $c$, if the character at the top of the stack is the same as $c$, we increment the count of the top element by one; otherwise, we push the character $c$ and count $1$ into the stack. When the count of the top element equals $k$, we pop the top element from the stack.
After traversing the string $s$, the elements remaining in the stack form the final result. We can pop the elements from the stack one by one, concatenate them into a string, and that’s our answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
t = []
i, n = 0, len(s)
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
cnt = j - i
cnt %= k
if t and t[-1][0] == s[i]:
t[-1][1] = (t[-1][1] + cnt) % k
if t[-1][1] == 0:
t.pop()
elif cnt:
t.append([s[i], cnt])
i = j
ans = [c * v for c, v in t]
return "".join(ans)
|
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
| class Solution {
public String removeDuplicates(String s, int k) {
Deque<int[]> stk = new ArrayDeque<>();
for (int i = 0; i < s.length(); ++i) {
int j = s.charAt(i) - 'a';
if (!stk.isEmpty() && stk.peek()[0] == j) {
stk.peek()[1] = (stk.peek()[1] + 1) % k;
if (stk.peek()[1] == 0) {
stk.pop();
}
} else {
stk.push(new int[] {j, 1});
}
}
StringBuilder ans = new StringBuilder();
for (var e : stk) {
char c = (char) (e[0] + 'a');
for (int i = 0; i < e[1]; ++i) {
ans.append(c);
}
}
ans.reverse();
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
string removeDuplicates(string s, int k) {
vector<pair<char, int>> stk;
for (char& c : s) {
if (stk.size() && stk.back().first == c) {
stk.back().second = (stk.back().second + 1) % k;
if (stk.back().second == 0) {
stk.pop_back();
}
} else {
stk.push_back({c, 1});
}
}
string ans;
for (auto [c, v] : stk) {
ans += string(v, c);
}
return ans;
}
};
|
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
| func removeDuplicates(s string, k int) string {
stk := []pair{}
for _, c := range s {
if len(stk) > 0 && stk[len(stk)-1].c == c {
stk[len(stk)-1].v = (stk[len(stk)-1].v + 1) % k
if stk[len(stk)-1].v == 0 {
stk = stk[:len(stk)-1]
}
} else {
stk = append(stk, pair{c, 1})
}
}
ans := []rune{}
for _, e := range stk {
for i := 0; i < e.v; i++ {
ans = append(ans, e.c)
}
}
return string(ans)
}
type pair struct {
c rune
v int
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stk = []
for c in s:
if stk and stk[-1][0] == c:
stk[-1][1] = (stk[-1][1] + 1) % k
if stk[-1][1] == 0:
stk.pop()
else:
stk.append([c, 1])
ans = [c * v for c, v in stk]
return "".join(ans)
|
