Partition string into two substrings having maximum number of common non | C ++ program to implement the above approach ; Function to count maximum common non - repeating characters that can be obtained by partitioning the string into two non - empty substrings ; Stores count of non - repeating characters present in both the substrings ; Stores distinct characters in left substring ; Stores distinct characters in right substring ; Traverse left substring ; Insert S [ i ] into ls ; Traverse right substring ; Insert S [ i ] into rs ; Traverse distinct characters of left substring ; If current character is present in right substring ; Update cnt ; Return count ; Function to partition the string into two non - empty substrings in all possible ways ; Stores maximum common distinct characters present in both the substring partitions ; Traverse the string ; Update ans ; Print count of maximum common non - repeating characters ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countCommonChar ( int ind , string & S ) { int cnt = 0 ; set < char > ls ; set < char > rs ; for ( int i = 0 ; i < ind ; ++ i ) { ls . insert ( S [ i ] ) ; } for ( int i = ind ; i < S . length ( ) ; ++ i ) { rs . insert ( S [ i ] ) ; } for ( auto v : ls ) { if ( rs . count ( v ) ) { ++ cnt ; } } return cnt ; } void partitionStringWithMaxCom ( string & S ) { int ans = 0 ; for ( int i = 1 ; i < S . length ( ) ; ++ i ) { ans = max ( ans , countCommonChar ( i , S ) ) ; } cout << ans << " STRNEWLINE " ; } int main ( ) { string str = " aabbca " ; partitionStringWithMaxCom ( str ) ; return 0 ; }