Maximum score possible by removing substrings made up of single distinct character | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isUnique ( string s ) { set < char > Set ; for ( char c : s ) { Set . insert ( c ) ; } return Set . size ( ) == 1 ; } 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 . substr ( i , j + 1 ) ; if ( isUnique ( sub ) ) mx = max ( mx , a [ sub . length ( ) - 1 ] + maxScore ( s . substr ( 0 , i ) + s . substr ( j + 1 ) , a ) ) ; } } return mx ; } int main ( ) { string s = "011" ; int a [ ] = { 1 , 3 , 1 } ; cout << maxScore ( s , a ) - 1 ; return 0 ; }