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 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
import java . util . * ; class GFG { static int countCommonChar ( int ind , String S ) { int cnt = 0 ; HashSet < Character > ls = new HashSet < Character > ( ) ; HashSet < Character > rs = new HashSet < Character > ( ) ; for ( int i = 0 ; i < ind ; ++ i ) { ls . add ( S . charAt ( i ) ) ; } for ( int i = ind ; i < S . length ( ) ; ++ i ) { rs . add ( S . charAt ( i ) ) ; } for ( char v : ls ) { if ( rs . contains ( v ) ) { ++ cnt ; } } return cnt ; } static void partitionStringWithMaxCom ( String S ) { int ans = 0 ; for ( int i = 1 ; i < S . length ( ) ; ++ i ) { ans = Math . max ( ans , countCommonChar ( i , S ) ) ; } System . out . print ( ans + "NEW_LINE"); } public static void main ( String [ ] args ) { String str = " aabbca " ; partitionStringWithMaxCom ( str ) ; } }