Count subsequences in first string which are anagrams of the second string | C ++ implementation to count subsequences in first string 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 program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define SIZE  26 NEW_LINE int binomialCoeff ( int n , int k ) { int res = 1 ; if ( k > n - k ) k = n - k ; for ( int i = 0 ; i < k ; ++ i ) { res *= ( n - i ) ; res /= ( i + 1 ) ; } return res ; } int countSubsequences ( string str1 , string str2 ) { int freq1 [ SIZE ] , freq2 [ SIZE ] ; int n1 = str1 . size ( ) ; int n2 = str2 . size ( ) ; memset ( freq1 , 0 , sizeof ( freq1 ) ) ; memset ( freq2 , 0 , sizeof ( freq2 ) ) ; for ( int i = 0 ; i < n1 ; i ++ ) freq1 [ str1 [ i ] - ' a ' ] ++ ; for ( int i = 0 ; i < n2 ; i ++ ) freq2 [ str2 [ i ] - ' a ' ] ++ ; int count = 1 ; for ( int 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 ; } int main ( ) { string str1 = " abacd " ; string str2 = " abc " ; cout << " Count ▁ = ▁ " << countSubsequences ( str1 , str2 ) ; return 0 ; }