Partition string into two substrings having maximum number of common non | 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
def countCommonChar ( ind , S ) : NEW_LINE INDENT cnt = 0 NEW_LINE ls = set ( ) NEW_LINE rs = set ( ) NEW_LINE for i in range ( ind ) : NEW_LINE INDENT ls . add ( S [ i ] ) NEW_LINE DEDENT for i in range ( ind , len ( S ) ) : NEW_LINE INDENT rs . add ( S [ i ] ) NEW_LINE DEDENT for v in ls : NEW_LINE INDENT if v in rs : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT return cnt NEW_LINE DEDENT def partitionStringWithMaxCom ( S ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( 1 , len ( S ) ) : NEW_LINE INDENT ans = max ( ans , countCommonChar ( i , S ) ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " aabbca " NEW_LINE partitionStringWithMaxCom ( string ) NEW_LINE DEDENT