1209. Remove All Adjacent Duplicates in String II LeetCode Solution
In this guide, you will get 1209. Remove All Adjacent Duplicates in String II LeetCode Solution with the best time and space complexity. The solution to Remove All Adjacent Duplicates in String II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 <= 105
2 <= k <= 104
s only contains lowercase English letters.
1209. Remove All Adjacent Duplicates in String II LeetCode Solution in C++
class Solution {
public:
string removeDuplicates(const string& s, int k) {
string ans;
vector<pair<char, int>> stack;
for (const char c : s)
if (stack.empty() || stack.back().first != c)
stack.emplace_back(c, 1);
else if (++stack.back().second == k) // stack[-1] == c
stack.pop_back();
for (const auto& [c, count] : stack)
ans.append(count, c);
return ans;
}
}; /* code provided by PROGIEZ */
1209. Remove All Adjacent Duplicates in String II LeetCode Solution in Java
class Item {
public char c;
public int freq;
public Item(char c, int freq) {
this.c = c;
this.freq = freq;
}
}
class Solution {
public String removeDuplicates(String s, int k) {
StringBuilder sb = new StringBuilder();
LinkedList<Item> stack = new LinkedList<>();
for (final char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek().c == c)
++stack.peek().freq;
else
stack.push(new Item(c, 1));
if (stack.peek().freq == k)
stack.pop();
}
while (!stack.isEmpty()) {
Item item = stack.pop();
for (int i = 0; i < item.freq; ++i)
sb.append(item.c);
}
return sb.reverse().toString();
}
} // code provided by PROGIEZ
1209. Remove All Adjacent Duplicates in String II LeetCode Solution in Python
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = []
for c in s:
if not stack or stack[-1][0] != c:
stack.append([c, 1])
else: # stack[-1][0] == c
stack[-1][1] += 1
if stack[-1][1] == k:
stack.pop()
return ''.join(c * count for c, count in stack) # code by PROGIEZ
