Split a string into maximum number of unique substrings | CPP program for the above approach ; Utility function to find maximum count of unique substrings by splitting the string ; Stores maximum count of unique substring by splitting the string into substrings ; Iterate over the characters of the string ; Stores prefix substring ; Check if the current substring already exists ; Insert tmp into set ; Recursively call for remaining characters of string ; Remove from the set ; Return answer ; Function to find the maximum count of unique substrings by splitting a string into maximum number of unique substrings ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxUnique ( string S , set < string > st ) { int mx = 0 ; for ( int i = 1 ; i <= S . length ( ) ; i ++ ) { string tmp = S . substr ( 0 , i ) ; if ( st . find ( tmp ) == st . end ( ) ) { st . insert ( tmp ) ; mx = max ( mx , maxUnique ( S . substr ( i ) , st ) + 1 ) ; st . erase ( tmp ) ; } } return mx ; } int maxUniqueSplit ( string S ) { set < string > st ; return maxUnique ( S , st ) ; } int main ( ) { string S = " ababccc " ; int res = maxUniqueSplit ( S ) ; cout << res ; }