Partition string into two substrings having maximum number of common non | Java 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
import java . util . * ; class GFG { static void countMaxCommonChar ( char [ ] S ) { LinkedHashSet < Character > Q = new LinkedHashSet < > ( ) ; int res = 1 ; HashMap < Character , Integer > freq = new HashMap < > ( ) ; for ( int i = 0 ; i < S . length ; i ++ ) { if ( freq . containsKey ( S [ i ] ) ) { freq . put ( S [ i ] , freq . get ( S [ i ] ) + 1 ) ; } else { freq . put ( S [ i ] , 1 ) ; } } for ( int i = 0 ; i < S . length ; i ++ ) { if ( freq . containsKey ( S [ i ] ) ) { freq . put ( S [ i ] , freq . get ( S [ i ] ) - 1 ) ; } if ( ! freq . containsKey ( S [ i ] ) ) { Q . remove ( S [ i ] ) ; } else { Q . add ( S [ i ] ) ; } int curr = Q . size ( ) - 1 ; res = Math . max ( res , curr ) ; } System . out . print ( res + "NEW_LINE"); } public static void main ( String [ ] args ) { String str = " aabbca " ; countMaxCommonChar ( str . toCharArray ( ) ) ; } }