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 distinct characters of S in sorted order ; Stores maximum common distinct characters present in both the partitions ; Stores frequency of each distinct character n the string S ; Traverse the string ; Update frequency of S [ i ] ; Traverse the string ; Decreasing frequency of S [ i ] ; If the frequency of S [ i ] is 0 ; Remove S [ i ] from Q ; Insert S [ i ] into Q ; Stores count of distinct characters in Q ; Update res ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE #include <ext/pb_ds/assoc_container.hpp> NEW_LINE #include <ext/pb_ds/tree_policy.hpp> NEW_LINE using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; template < typename T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update > ; int countMaxCommonChar ( string & S ) { ordered_set < char > Q ; int res = 0 ; map < char , int > freq ; for ( int i = 0 ; i < S . length ( ) ; i ++ ) { freq [ S [ i ] ] ++ ; } for ( int i = 0 ; i < S . length ( ) ; i ++ ) { freq [ S [ i ] ] -- ; if ( ! freq [ S [ i ] ] ) { Q . erase ( S [ i ] ) ; } else { Q . insert ( S [ i ] ) ; } int curr = Q . size ( ) ; res = max ( res , curr ) ; } cout << res << " STRNEWLINE " ; } int main ( ) { string str = " aabbca " ; countMaxCommonChar ( str ) ; return 0 ; }