Restrictive Candy Crush

A string s is to be reduced by following this:

group of k consecutive identical characters should be removed

example: given string codddooe, and k =3

now in the first phase , ddd are consecutive identical characters  with k=3 elements so this is removed and the string is coooe

now in second phase, ooo are consecutive identical characters  with k=3 elements so this is removed and the string is ce

now there are no consecutive identical characters  with k=3 elements so the output should be ce



Example 1:

Input:
k = 2
s = "codemummy"
Output:
codemuy
Explanation:
Modified String after each step: 
"codemummy" -> "codemuy"


Example 2:

Input:
k = 2
s = "codemummu" 
Output:
codem
Explanation:
Modified String after each step:
"codemummu" -> "codemuu" -> "codem"





method :

Use a stack to store the characters, when there are k identical characters, delete them.

traversing through the string (s) , and push the elment into the stack(st) and even the count of consecutive identical element count. so we are pushing pair(s[i],count)

and if the stack top element is same as the element s[i] and count of stack top element +1 is equal to k, remove k elements from stack

and if the stack top element is same as the element s[i] and count of stack top element +1 is not equal to k, then push that element on to stack with count increased by 1.




c++ implementation:

string Reduced_String(int k,string s)
 {
        stack<pair<char,int>> st;
        string r="";
        
        if(k == 1){
            return r;
        }
        
        
        for(int i=0;i<s.size();i++)
        {
            if(st.empty())
            {
                st.push({s[i],1});
            }
            else if(st.top().first==s[i])
            {
    
                if(st.top().second+1==k)
                {
                    int z=k-1;
                    while(z){
                        st.pop();
                        z--;
                    }
                }
                else
                {
                    st.push({s[i],st.top().second+1});
                }
                
            }
            else 
            {
                st.push({s[i],1});
            }
        }
        
        while(!st.empty()){
            r+=st.top().first;
            st.pop();
        }
        reverse(r.begin(),r.end());
        return r;
    }

Time Complexity: O(n) 
space Complexity: O(n) 
where n is the length of the string

darkmode