Maximum score possible by removing substrings made up of single distinct character | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; map < string , int > dp ; int maxScore ( string s , vector < int > a ) { if ( dp . find ( s ) != dp . end ( ) ) return dp [ s ] ; int n = s . size ( ) ; if ( n == 0 ) return 0 ; if ( n == 1 ) return a [ 0 ] ; int head = 0 ; int mx = -1 ; while ( head < n ) { int tail = head ; while ( tail < n ) { if ( s [ tail ] != s [ head ] ) { head = tail ; break ; } string sub = s . substr ( head , tail + 1 ) ; mx = max ( mx , a [ sub . size ( ) - 1 ] + maxScore ( s . substr ( 0 , head ) + s . substr ( tail + 1 , s . size ( ) ) , a ) ) ; tail += 1 ; } if ( tail == n ) break ; } dp [ s ] = mx ; return mx ; } int main ( ) { string s = " abb " ; vector < int > a = { 1 , 3 , 1 } ; cout << ( maxScore ( s , a ) - 1 ) ; }