Maximum score possible by removing substrings made up of single distinct character | Java program for the above approach ; Function to check if the string s consists of a single distinct character or not ; Function to calculate the maximum score possible by removing substrings ; If string is empty ; If length of string is 1 ; Store the maximum result ; Try to remove all substrings that satisfy the condition and check for resultant string after removal ; Store the substring { s [ i ] , . . , s [ j ] } ; Check if the substring contains only a single distinct character ; Return the maximum score ; Driver Code
import java . util . * ; class GFG { static boolean isUnique ( String s ) { HashSet < Character > set = new HashSet < > ( ) ; for ( char c : s . toCharArray ( ) ) set . add ( c ) ; return set . size ( ) == 1 ; } static int maxScore ( String s , int [ ] a ) { int n = s . length ( ) ; if ( n == 0 ) return 0 ; if ( n == 1 ) return a [ 0 ] ; int mx = - 1 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i ; j < n ; j ++ ) { String sub = s . substring ( i , j + 1 ) ; if ( isUnique ( sub ) ) mx = Math . max ( mx , a [ sub . length ( ) - 1 ] + maxScore ( s . substring ( 0 , i ) + s . substring ( j + 1 ) , a ) ) ; } } return mx ; } public static void main ( String args [ ] ) { String s = "011" ; int a [ ] = { 1 , 3 , 1 } ; System . out . print ( maxScore ( s , a ) ) ; } }