Maximize cost of removing all occurrences of substrings " ab " and " ba " | Java 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
import java . util . * ; class GFG { public static int MaxCollection ( String S , int P , int Q ) { char maxstr [ ] = ( P >= Q ? " ab " : " ba " ) . toCharArray ( ) ; char minstr [ ] = ( P >= Q ? " ba " : " ab " ) . toCharArray ( ) ; int maxp = Math . max ( P , Q ) ; int minp = Math . min ( P , Q ) ; int cost = 0 ; Stack < Character > stack1 = new Stack < > ( ) ; char [ ] s = S . toCharArray ( ) ; for ( char ch : s ) { if ( ! stack1 . isEmpty ( ) && ( stack1 . peek ( ) == maxstr [ 0 ] && ch == maxstr [ 1 ] ) ) { stack1 . pop ( ) ; cost += maxp ; } else { stack1 . push ( ch ) ; } } StringBuilder sb = new StringBuilder ( ) ; while ( ! stack1 . isEmpty ( ) ) sb . append ( stack1 . pop ( ) ) ; sb = sb . reverse ( ) ; String remstr = sb . toString ( ) ; for ( char ch : remstr . toCharArray ( ) ) { if ( ! stack1 . isEmpty ( ) && ( stack1 . peek ( ) == minstr [ 0 ] && ch == minstr [ 1 ] ) ) { stack1 . pop ( ) ; cost += minp ; } else { stack1 . push ( ch ) ; } } return cost ; } public static void main ( String [ ] args ) { String S = " cbbaabbaab " ; int P = 6 ; int Q = 4 ; System . out . println ( MaxCollection ( S , P , Q ) ) ; } }