Maximize cost of removing all occurrences of substrings " ab " and " ba " | 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
def MaxCollection ( S , P , Q ) : NEW_LINE INDENT maxstr = [ i for i in ( " ab " if P >= Q else " ba " ) ] NEW_LINE minstr = [ i for i in ( " ba " if P >= Q else " ab " ) ] NEW_LINE maxp = max ( P , Q ) NEW_LINE minp = min ( P , Q ) NEW_LINE cost = 0 NEW_LINE stack1 = [ ] NEW_LINE s = [ i for i in S ] NEW_LINE for ch in s : NEW_LINE INDENT if ( len ( stack1 ) > 0 and ( stack1 [ - 1 ] == maxstr [ 0 ] and ch == maxstr [ 1 ] ) ) : NEW_LINE INDENT del stack1 [ - 1 ] NEW_LINE cost += maxp NEW_LINE DEDENT else : NEW_LINE INDENT stack1 . append ( ch ) NEW_LINE DEDENT DEDENT sb = " " NEW_LINE while ( len ( stack1 ) > 0 ) : NEW_LINE INDENT sb += stack1 [ - 1 ] NEW_LINE del stack1 [ - 1 ] NEW_LINE DEDENT sb = sb [ : : - 1 ] NEW_LINE remstr = sb NEW_LINE for ch in remstr : NEW_LINE INDENT if ( len ( stack1 ) > 0 and ( stack1 [ - 1 ] == minstr [ 0 ] and ch == minstr [ 1 ] ) ) : NEW_LINE INDENT del stack1 [ - 1 ] NEW_LINE cost += minp NEW_LINE DEDENT else : NEW_LINE INDENT stack1 . append ( ch ) NEW_LINE DEDENT DEDENT return cost NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = " cbbaabbaab " NEW_LINE P = 6 ; NEW_LINE Q = 4 ; NEW_LINE print ( MaxCollection ( S , P , Q ) ) ; NEW_LINE DEDENT