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][0] != c:
                stack.append([c, 1])
                
            # otherwise, increment the count
            else:
                stack[-1][1] += 1
                
            # if the count reaches k, remove all k characters from the stack
            if stack[-1][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();
    }
}