Count ways to partition a string such that both parts have equal distinct characters | Java implementation to count the number of ways to partition the String such that each partition have same number of distinct characters in the String ; 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
class GFG { static int distinctChars ( String s ) { int freq [ ] = new int [ 26 ] ; int count = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) freq [ s . charAt ( i ) - ' a ' ] ++ ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( freq [ i ] > 0 ) count ++ ; } return count ; } static int waysToSplit ( String s ) { int n = s . length ( ) ; int answer = 0 ; for ( int i = 1 ; i < n ; i ++ ) { String left = s . substring ( 0 , i ) ; String right = s . substring ( i , n ) ; if ( distinctChars ( left ) == distinctChars ( right ) ) answer ++ ; } return answer ; } public static void main ( String [ ] args ) { String s = " ababa " ; System . out . print ( waysToSplit ( s ) ) ; } }