TSUNADE - Editorial

editorial
1

PROBLEM LINK:

[Practice]([LEAF101 Problem - CodeChef]

Div-2 Contest

Author: Venkatesh G Dhongadi
Tester: Venkatesh G Dhongadi
Editorialist: Venkatesh G Dhongadi

DIFFICULTY:

Easy-Medium

PROBLEM:

Welcome back to the hidden leaf village!
The 5th Hokage of the Hidden leaf village Lady Tsunade is a very superstitious person.
She believes in everything from black magic to cats crossing your path.
Today her horoscope tells her to avoid K numbers as much as possible. She comes across a string of lowercase english letters which has multiple consecutive occurrences of the same character and starts panicking.
To get rid of all such occurrences from the string, she alots this task to the hidden leaf’s most intelligent person ‘Shikamaru Nara’.
Can you help Shikamaru help Tsunade get rid of consecutive appearances of any character in the given lowercase string?

PREREQUISITES:

Stacks

QUICK EXPLANATION:

This question is based on the logic stacks

EXPLANATION:

The naive approach would be to repeatedly keep looking K for repeated occurrences in the string and keep removing them. This approach is not good and will result in O(n^2) complexity in the worst case. A case where this strategy can go is ababababbababba.
A better strategy would be to maintain a stack with the count of the number of times the same character is pushed immediately below the current element and remove all the occurrences of the element immediately below once the count for that letter reaches K.

SOLUTIONS:

Setter's Solution 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, k; cin>>n>>k; 
    stack<pair<char, int> > st;
    string s; cin>>s; 

    for(char ch: s){
        if(st.empty() || ch != st.top().first)st.push({ch, 1}); 
        else st.push({ch, st.top().second + 1}); 
        
        while(!st.empty() && st.top().second >= k){
            for(int i = 0;i < k; ++i)st.pop(); 
        }
 }

    string ans = ""; 
    while(!st.empty())ans += st.top().first, st.pop(); 
    reverse(ans.begin(), ans.end()); 
    cout<<ans<<"\n"; 
    return 0;
}