Count ways to partition a string such that both parts have equal distinct characters | Function to count the number of ways to partition the string such that each partition have same number of distinct character ; Prefix and suffix array for distinct character from start and end ; To check whether a character has appeared till ith index ; Calculating prefix array ; Character appears for the first time in string ; Character is visited ; Resetting seen for suffix calculation ; Calculating the suffix array ; Character appears for the first time ; This character has now appeared ; Loop to calculate the number partition points in the string ; Check whether number of distinct characters are equal ; Driver Code
def waysToSplit ( s ) : NEW_LINE INDENT n = len ( s ) ; NEW_LINE answer = 0 ; NEW_LINE prefix = [ 0 ] * n ; NEW_LINE suffix = [ 0 ] * n ; NEW_LINE seen = [ 0 ] * 26 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT prev = prefix [ i - 1 ] if ( i - 1 >= 0 ) else 0 ; NEW_LINE if ( seen [ ord ( s [ i ] ) - ord ( ' a ' ) ] == 0 ) : NEW_LINE INDENT prefix [ i ] += ( prev + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT prefix [ i ] = prev ; NEW_LINE DEDENT seen [ ord ( s [ i ] ) - ord ( ' a ' ) ] = 1 ; NEW_LINE DEDENT seen = [ 0 ] * len ( seen ) ; NEW_LINE suffix [ n - 1 ] = 0 ; NEW_LINE for i in range ( n - 1 , 0 , - 1 ) : NEW_LINE INDENT prev = suffix [ i ] ; NEW_LINE if ( seen [ ord ( s [ i ] ) - ord ( ' a ' ) ] == 0 ) : NEW_LINE INDENT suffix [ i - 1 ] += ( prev + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT suffix [ i - 1 ] = prev ; NEW_LINE DEDENT seen [ ord ( s [ i ] ) - ord ( ' a ' ) ] = 1 ; NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( prefix [ i ] == suffix [ i ] ) : 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