Maximum score possible by removing substrings made up of single distinct character | Java 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
import java . util . * ; class GFG { static Map < String , Integer > dp = new HashMap < > ( ) ; static int maxScore ( String s , int [ ] a ) { if ( dp . containsKey ( s ) ) return dp . get ( 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 . charAt ( tail ) != s . charAt ( head ) ) { head = tail ; break ; } String sub = s . substring ( head , tail + 1 ) ; mx = Math . max ( mx , a [ sub . length ( ) - 1 ] + maxScore ( s . substring ( 0 , head ) + s . substring ( tail + 1 , s . length ( ) ) , a ) ) ; tail += 1 ; } if ( tail == n ) break ; } dp . put ( s , mx ) ; return mx ; } public static void main ( String [ ] args ) { String s = " abb " ; int [ ] a = { 1 , 3 , 1 } ; System . out . println ( ( maxScore ( s , a ) ) ) ; } }