Reduce the string by removing K consecutive identical characters | CPP program for the above approach ; Basic Approach is to create a Stack that store the Character and its continuous repetition number This is done using pair < char , int > Further we check at each iteration , whether the character matches the top of stack if it does then check for number of repetitions else add to top of stack with count 1 ; Base Case If k = 1 then all characters can be removed at each instance ; initialize string ; create a stack using pair < > for storing each character and corresponding repetition ; iterate through the string ; if stack is empty then simply add the character with count 1 else check if character is same as top of stack ; if character at top of stack is same as current character increase the number of repetitions in the top of stack by 1 ; if character at top of stack is not same as current character push the character along with count 1 into the top of stack ; Iterate through the stack Use string ( int , char ) in order to replicate the character multiple times and convert into string then add in front of output string ; Driver Code
#include <bits/stdc++.h> NEW_LINE #include <iostream> NEW_LINE using namespace std ; class Solution { public : string remove_k_char ( int k , string s ) { if ( k == 1 ) return " " ; string output = " " ; stack < pair < char , int > > stk ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( stk . empty ( ) == true ) { stk . push ( make_pair ( s [ i ] , 1 ) ) ; } else { if ( s [ i ] == ( stk . top ( ) ) . first ) { stk . push ( { s [ i ] , stk . top ( ) . second + 1 } ) ; if ( stk . top ( ) . second == k ) { int x = k ; while ( x ) { stk . pop ( ) ; x -- ; } } } else { stk . push ( make_pair ( s [ i ] , 1 ) ) ; } } } while ( ! stk . empty ( ) ) { output += stk . top ( ) . first ; stk . pop ( ) ; } reverse ( output . begin ( ) , output . end ( ) ) ; return output ; } } ; int main ( ) { string s = " geeksforgeeks " ; int k = 2 ; Solution obj ; cout << obj . remove_k_char ( k , s ) << " STRNEWLINE " ; return 0 ; }