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
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); Stackcounts = 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;ix.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(); } }