Algorithm
Problem Name: 1209. Remove All Adjacent Duplicates in String II
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 <= 104sonly contains lowercase English letters.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String removeDuplicates(String s, int k) {
Stack stack = new Stack<>();
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek().c == c) {
stack.peek().count++;
} else {
stack.push(new CharPair(c));
}
if (stack.peek().count == k) {
stack.pop();
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
CharPair pair = stack.pop();
for (int i = 0; i < pair.count; i++) {
sb.append(pair.c);
}
}
return sb.reverse().toString();
}
private static class CharPair {
char c;
int count;
public CharPair(char c) {
this.c = c;
this.count = 1;
}
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const removeDuplicates = function (s, k) {
const stack = [];
const arr = s.split('')
for(let i = 0; i < arr.length; i++) {
if(i === 0 || arr[i] !== arr[i - 1]) {
stack.push(1)
} else {
stack[stack.length - 1]++
if(stack[stack.length - 1] === k) {
stack.pop()
arr.splice(i - k + 1, k)
i -= k
}
}
}
return arr.join('')
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = []
for i, c in enumerate(s):
if not stack or stack[-1][0] != c:
stack.append([c, 1])
else:
stack[-1][1] += 1
if stack[-1][1] == k:
stack.pop()
return ''.join(k * v for k, v in stack)
Input
Output