Count subsequences in first string which are anagrams of the second string | PHP implementation to count subsequences in first $which are anagrams of the second string ; Returns value of Binomial Coefficient C ( n , k ) ; Since C ( n , k ) = C ( n , n - k ) ; Calculate value of [ n * ( n - 1 ) * -- - * ( n - k + 1 ) ] / [ k * ( k - 1 ) * -- -- * 1 ] ; function to count subsequences in first string which are anagrams of the second string ; hash tables to store frequencies of each character ; store frequency of each character of ' str1' ; store frequency of each character of ' str2' ; to store the total count of subsequences ; if character ( i + ' a ' ) exists in ' str2' ; if this character ' s ▁ frequency ▁ ▁ in ▁ ' str2 ' ▁ in ▁ less ▁ than ▁ or ▁ ▁ equal ▁ to ▁ its ▁ frequency ▁ in ▁ ▁ ' str1 ' ▁ then ▁ accumulate ▁ its ▁ ▁ contribution ▁ to ▁ the ▁ count ▁ ▁ of ▁ subsequences . ▁ If ▁ its ▁ ▁ frequency ▁ in ▁ ' str1 ' ▁ is ▁ ' n ' ▁ ▁ and ▁ in ▁ ' str2 ' ▁ is ▁ ' r ', then  its contribution will be nCr,  where C is the binomial  coefficient. ; else return 0 as there could be no subsequence which is an anagram of ' str2' ; required count of subsequences ; Driver Code
< ? php $ SIZE = 26 ; function binomialCoeff ( $ n , $ k ) { $ res = 1 ; if ( $ k > $ n - $ k ) $ k = $ n - $ k ; for ( $ i = 0 ; $ i < $ k ; ++ $ i ) { $ res *= ( $ n - $ i ) ; $ res /= ( $ i + 1 ) ; } return $ res ; } function countSubsequences ( $ str1 , $ str2 ) { global $ SIZE ; $ freq1 = array ( ) ; $ freq2 = array ( ) ; for ( $ i = 0 ; $ i < $ SIZE ; $ i ++ ) { $ freq1 [ $ i ] = 0 ; $ freq2 [ $ i ] = 0 ; } $ n1 = strlen ( $ str1 ) ; $ n2 = strlen ( $ str2 ) ; for ( $ i = 0 ; $ i < $ n1 ; $ i ++ ) $ freq1 [ ord ( $ str1 [ $ i ] ) - ord ( ' a ' ) ] ++ ; for ( $ i = 0 ; $ i < $ n2 ; $ i ++ ) $ freq2 [ ord ( $ str2 [ $ i ] ) - ord ( ' a ' ) ] ++ ; $ count = 1 ; for ( $ i = 0 ; $ i < $ SIZE ; $ i ++ ) if ( $ freq2 [ $ i ] != 0 ) { if ( $ freq2 [ $ i ] <= $ freq1 [ $ i ] ) $ count = $ count * binomialCoeff ( $ freq1 [ $ i ] , $ freq2 [ $ i ] ) ; else return 0 ; } return $ count ; } $ str1 = " abacd " ; $ str2 = " abc " ; echo ( " Count ▁ = ▁ " . countSubsequences ( $ str1 , $ str2 ) ) ; ? >