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
function waysToSplit ( s ) { var n = s . length ; var answer = 0 ; var prefix = Array ( n ) . fill ( 0 ) ; var suffix = Array ( n ) . fill ( 0 ) ; var seen = Array ( 26 ) . fill ( 0 ) ; for ( var i = 0 ; i < n ; i ++ ) { var prev = ( i - 1 >= 0 ? prefix [ i - 1 ] : 0 ) ; if ( seen [ s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] == 0 ) { prefix [ i ] += ( prev + 1 ) ; } else prefix [ i ] = prev ; seen [ s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] = 1 ; } seen = Array ( 26 ) . fill ( 0 ) ; suffix [ n - 1 ] = 0 ; for ( var i = n - 1 ; i >= 1 ; i -- ) { var prev = suffix [ i ] ; if ( seen [ s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] == 0 ) { suffix [ i - 1 ] += ( prev + 1 ) ; } else suffix [ i - 1 ] = prev ; seen [ s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ] = 1 ; } for ( var i = 0 ; i < n ; i ++ ) { if ( prefix [ i ] == suffix [ i ] ) answer ++ ; } return answer ; } var s = " " ; document . write ( waysToSplit ( s ) ) ;