# 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)