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
using System ; using System . Collections . Generic ; class GFG { static Dictionary < string , int > dp = new Dictionary < string , int > ( ) ; static int maxScore ( string s , int [ ] a ) { if ( dp . ContainsKey ( s ) ) return dp [ s ] ; int n = s . Length ; 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 . Substring ( head , tail + 1 - head ) ; mx = Math . Max ( mx , a [ sub . Length - 1 ] + maxScore ( s . Substring ( 0 , head ) + s . Substring ( tail + 1 , s . Length - tail - 1 ) , a ) ) ; tail += 1 ; } if ( tail == n ) break ; } dp . Add ( s , mx ) ; return mx ; } static public void Main ( ) { string s = " abb " ; int [ ] a = { 1 , 3 , 1 } ; Console . WriteLine ( ( maxScore ( s , a ) ) ) ; } }