Count ways to partition a string such that both parts have equal distinct characters | Function to count the distinct characters in the string ; Frequency of each character ; Loop to count the frequency of each character of the string ; If frequency is greater than 0 then the character occured ; Function to count the number of ways to partition the string such that each partition have same number of distinct character ; Loop to choose the partition index for the string ; Divide in two parts ; Check whether number of distinct characters are equal ; Driver Code
def distinctChars ( s ) : NEW_LINE INDENT freq = [ 0 ] * 26 ; NEW_LINE count = 0 ; NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT freq [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 ; NEW_LINE DEDENT for i in range ( 26 ) : NEW_LINE INDENT if ( freq [ i ] > 0 ) : NEW_LINE INDENT count += 1 ; NEW_LINE DEDENT DEDENT return count ; NEW_LINE DEDENT def waysToSplit ( s ) : NEW_LINE INDENT n = len ( s ) ; NEW_LINE answer = 0 ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT left = s [ 0 : i ] ; NEW_LINE right = s [ i : n ] ; NEW_LINE if ( distinctChars ( left ) == distinctChars ( right ) ) : NEW_LINE INDENT answer += 1 ; NEW_LINE DEDENT DEDENT return answer ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " ababa " ; NEW_LINE print ( waysToSplit ( s ) ) ; NEW_LINE DEDENT