Maximize cost obtained by removal of substrings " pr " or " rp " from a given String | 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
def swapXandY ( str , X , Y ) : NEW_LINE INDENT N = len ( str ) NEW_LINE X , Y = Y , X NEW_LINE for i in range ( N ) : NEW_LINE DEDENT ' NEW_LINE INDENT if ( str [ i ] == ' p ' ) : NEW_LINE INDENT str [ i ] = ' r ' NEW_LINE DEDENT elif ( str [ i ] == ' r ' ) : NEW_LINE INDENT str [ i ] = ' p ' NEW_LINE DEDENT DEDENT def maxCost ( str , X , Y ) : NEW_LINE INDENT N = len ( str ) NEW_LINE if ( Y > X ) : NEW_LINE INDENT swapXandY ( str , X , Y ) NEW_LINE DEDENT res = 0 NEW_LINE countP = 0 NEW_LINE countR = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( str [ i ] == ' p ' ) : NEW_LINE INDENT countP += 1 NEW_LINE DEDENT elif ( str [ i ] == ' r ' ) : NEW_LINE INDENT if ( countP > 0 ) : NEW_LINE INDENT countP -= 1 NEW_LINE res += X NEW_LINE DEDENT else : NEW_LINE INDENT countR += 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT res += min ( countP , countR ) * Y NEW_LINE countP = 0 NEW_LINE countR = 0 NEW_LINE DEDENT DEDENT res += min ( countP , countR ) * Y NEW_LINE return res NEW_LINE DEDENT str = " abppprrr " NEW_LINE X = 5 NEW_LINE Y = 4 NEW_LINE print ( maxCost ( str , X , Y ) ) NEW_LINE