Maximize cost of removing all occurrences of substrings " ab " and " ba " | C ++ program for the above approach : ; Function to find the maximum cost of removing substrings " ab " and " ba " from S ; MaxStr is the substring char array with larger cost ; MinStr is the substring char array with smaller cost ; ; Denotes larger point ; Denotes smaller point ; Stores cost scored ; Stack to keep track of characters ; Traverse the string ; If the substring is maxstr ; Pop from the stack ; Add maxp to cost ; Push the character to the stack ; Remaining string after removing maxstr ; Find remaining string ; Reversing the string retrieved from the stack ; Removing all occurences of minstr ; If the substring is minstr ; Pop from the stack ; Add minp to the cost ; Otherwise ; Return the maximum cost ; Driver Code ; Input String ; Costs
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MaxCollection ( string S , int P , int Q ) { char maxstr [ 2 ] ; string x = ( P >= Q ? " ab " : " ba " ) ; strcpy ( maxstr , x . c_str ( ) ) ; char minstr [ 2 ] ; x = ( P >= Q ? " ba " : " ab " ) ; strcpy ( minstr , x . c_str ( ) ) ; int maxp = max ( P , Q ) ; int minp = min ( P , Q ) ; int cost = 0 ; stack < char > stack1 ; char s [ S . length ( ) ] ; strcpy ( s , S . c_str ( ) ) ; for ( auto & ch : s ) { if ( ! stack1 . empty ( ) && ( stack1 . top ( ) == maxstr [ 0 ] && ch == maxstr [ 1 ] ) ) { stack1 . pop ( ) ; cost += maxp ; } else { stack1 . push ( ch ) ; } } string sb = " " ; while ( stack1 . size ( ) > 0 ) { sb = sb + stack1 . top ( ) ; stack1 . pop ( ) ; } reverse ( sb . begin ( ) , sb . end ( ) ) ; for ( auto & ch : sb ) { if ( ! stack1 . empty ( ) && ( stack1 . top ( ) == minstr [ 0 ] && ch == minstr [ 1 ] ) ) { stack1 . pop ( ) ; cost += minp ; } else { stack1 . push ( ch ) ; } } return cost ; } int main ( ) { string S = " cbbaabbaab " ; int P = 6 ; int Q = 4 ; cout << MaxCollection ( S , P , Q ) ; return 0 ; }