Remove All Adjacent Duplicates In String Ii - Leetcode Solution

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<pair<char,int>> 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).

1