Maximize cost obtained by removal of substrings " pr " or " rp " from a given String | C ++ Program to implement the above approach ; Function to maintain the case , X >= Y ; To maintain X >= Y ; Replace ' p ' to ' r ' ; Replace ' r ' to ' p ' . ; Function to return the maximum cost ; Stores the length of the string ; To maintain X >= Y . ; Stores the maximum cost ; Stores the count of ' p ' after removal of all " pr " substrings up to str [ i ] ; Stores the count of ' r ' after removal of all " pr " substrings up to str [ i ] ; Stack to maintain the order of characters after removal of substrings ; If substring " pr " is removed ; Increase cost by X ; If any substring " rp " left in the Stack ; If any substring " rp " left in the Stack ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool swapXandY ( string & str , int X , int Y ) { int N = str . length ( ) ; swap ( X , Y ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( str [ i ] == ' p ' ) { str [ i ] = ' r ' ; } else if ( str [ i ] == ' r ' ) { str [ i ] = ' p ' ; } } } int maxCost ( string str , int X , int Y ) { int N = str . length ( ) ; if ( Y > X ) { swapXandY ( str , X , Y ) ; } int res = 0 ; int countP = 0 ; int countR = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( str [ i ] == ' p ' ) { countP ++ ; } else if ( str [ i ] == ' r ' ) { if ( countP > 0 ) { countP -- ; res += X ; } else countR ++ ; } else { res += min ( countP , countR ) * Y ; countP = 0 ; countR = 0 ; } } res += min ( countP , countR ) * Y ; return res ; } int main ( ) { string str = " abppprrr " ; int X = 5 , Y = 4 ; cout << maxCost ( str , X , Y ) ; }