# Solution For Remove All Adjacent Duplicates In String Ii

Problem Statement:

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:

Input: s = “deeedbbcccbdaa”, k = 3
Output: “aa”

Input: s = “pbbcggttciiippooaais”, k = 2
Output: “ps”

Solution:

The problem can be solved using a stack data structure. We traverse the given string s and push each character onto the stack. If the top k-1 characters of the stack are equal to the current character, we pop them, as they form a sequence of k equal characters. This is repeated until the stack is empty or the top k-1 characters are not equal to the current character.

At the end of the traversal, we build the final string by popping the remaining characters from the stack and appending them to the result.

Code:

class Solution {
public:
string removeDuplicates(string s, int k) {
stack> st;
for(auto c: s){
if(st.empty() || st.top().first!=c){
st.push({c,1});
}
else{
st.top().second++;
if(st.top().second==k){
st.pop();
}
}
}
string ans =””;
while(!st.empty()){
auto p = st.top();
st.pop();
ans = string(p.second,p.first)+ans;
}
return ans;
}
};

Time Complexity:

The time complexity of the above solution is O(n), where n is the length of the given string s. This is because we traverse the string s once, and each character is processed only once. The time complexity of stack push and pop operations is considered to be O(1).

Space Complexity:

The space complexity of the above solution is O(n), where n is the length of the given string s. This is because we store a pair containing a character and its frequency for each character in the stack. The maximum number of such pairs that can be present in the stack at any point is n/k, which gives us a space complexity of O(n).

## Step by Step Implementation For Remove All Adjacent Duplicates In String Ii

```public String removeDuplicates(String s, int k) {
StringBuilder sb = new StringBuilder(s);
Stack counts = new Stack<>();
for (int i = 0; i < sb.length(); i++) {
if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) {
counts.push(1);
} else {
int inc = counts.pop() + 1;
if (inc == k) {
sb.delete(i - k + 1, i + 1);
i = i - k;
} else {
counts.push(inc);
}
}
}
return sb.toString();
}```
```class Solution:
def removeDuplicates(self, s: str, k: int) -> str:

# keep track of the number of times a character has been seen consecutively
# using a stack
stack = []

# iterate through the string
for c in s:

# if the stack is empty or the character at the top of the stack
# is not the same as the current character, reset the count
if not stack or stack[-1] != c:
stack.append([c, 1])

# otherwise, increment the count
else:
stack[-1] += 1

# if the count reaches k, remove all k characters from the stack
if stack[-1] == k:
stack.pop()

# return the remaining characters in the stack as a string
return "".join(c * k for c, k in stack)```
```var removeDuplicates = function(s, k) {
let stack = [];

for(let i=0;i x.c).join("");
};```
```class Solution {
public:
string removeDuplicates(string s, int k) {

// create a stack to keep track of the character and the count
stack> stk;

// iterate through the string
for (auto ch : s) {

// if the stack is empty or the character on the top of the stack is not equal to the current character
// push the character onto the stack
if (stk.empty() || stk.top().first != ch) {
stk.push({ch, 1});
}

// else if the character on the top of the stack is equal to the current character
// increment the count
else {
auto [topCh, topCount] = stk.top();
stk.pop();
topCount++;

// if the count is equal to k, then we have found a sequence of k characters that are equal
// so we can remove them from the string
if (topCount == k) {
continue;
}

// else push the character and count back onto the stack
stk.push({topCh, topCount});
}
}

// create a new string and push the characters from the stack onto the string
string res = "";
while (!stk.empty()) {
auto [topCh, topCount] = stk.top();
stk.pop();
res = string(topCount, topCh) + res;
}

return res;
}
};```
```public class Solution {
public string RemoveDuplicates(string s, int k) {
// Base case
if (s == null || s.Length == 0 || k <= 1) return s;

StringBuilder sb = new StringBuilder(s.Length);
Stack<(char, int)> stack = new Stack<(char, int)>();

for (int i = 0; i < s.Length; i++)
{
char c = s[i];

// If the stack is not empty and the top element is equal to the current character
if (stack.Count != 0 && stack.Peek().Item1 == c)
{
// Increment the count of the top element
var top = stack.Pop();
top.Item2++;

// If the count is less than k, push the element back onto the stack
if (top.Item2 < k)
stack.Push(top);
}
// Otherwise, push a new element onto the stack
else
stack.Push((c, 1));
}

// Append all remaining elements to the string builder
foreach (var element in stack)
for (int i = 0; i < element.Item2; i++)
sb.Append(element.Item1);

return sb.ToString();
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]