Maximum score possible by removing substrings made up of single distinct character | Initialize a dictionary to store the precomputed results ; Function to calculate the maximum score possible by removing substrings ; If s is present in dp [ ] array ; Base Cases : ; If length of string is 0 ; If length of string is 1 ; Put head pointer at start ; Initialize the max variable ; Generate the substrings using two pointers ; If s [ head ] and s [ tail ] are different ; Move head to tail and break ; Store the substring ; Update the maximum ; Move the tail ; Store the score ; Driver Code
dp = dict ( ) NEW_LINE def maxScore ( s , a ) : NEW_LINE INDENT if s in dp : NEW_LINE INDENT return dp [ s ] NEW_LINE DEDENT n = len ( s ) NEW_LINE if n == 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT if n == 1 : NEW_LINE INDENT return a [ 0 ] NEW_LINE DEDENT head = 0 NEW_LINE mx = - 1 NEW_LINE while head < n : NEW_LINE INDENT tail = head NEW_LINE while tail < n : NEW_LINE INDENT if s [ tail ] != s [ head ] : NEW_LINE INDENT head = tail NEW_LINE break NEW_LINE DEDENT sub = s [ head : tail + 1 ] NEW_LINE mx = max ( mx , a [ len ( sub ) - 1 ] + maxScore ( s [ : head ] + s [ tail + 1 : ] , a ) ) NEW_LINE tail += 1 NEW_LINE DEDENT if tail == n : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT dp [ s ] = mx NEW_LINE return mx NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " abb " NEW_LINE a = [ 1 , 3 , 1 ] NEW_LINE print ( maxScore ( s , a ) ) NEW_LINE DEDENT