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
let dp = new Map ( ) ; function maxScore ( s , a ) { if ( dp . has ( s ) ) return dp . get ( s ) ; let n = s . length ; if ( n == 0 ) return 0 ; if ( n == 1 ) return a [ 0 ] ; let head = 0 ; let mx = - 1 ; while ( head < n ) { let tail = head ; while ( tail < n ) { if ( s [ tail ] != s [ head ] ) { head = tail ; break ; } let sub = s . substring ( head , head + tail + 1 ) ; mx = Math . max ( mx , a [ sub . length - 1 ] + maxScore ( s . substring ( 0 , head ) + s . substring ( tail + 1 , tail + 1 + s . length ) , a ) ) ; tail += 1 ; } if ( tail == n ) break ; } dp . set ( s , mx ) ; return mx ; } let s = " " ; let a = [ 1 , 3 , 1 ] ; document . write ( ( maxScore ( s , a ) ) - 1 ) ;