Given two strings str1 and str2 of length n1 and n2 respectively. The problem is to count all the subsequences of str1 which are anagrams of str2.
Examples:
Input : str1 = "abacd", str2 = "abc"
Output : 2
Index of characters in the 2 subsequences are:
{0, 1, 3} = {a, b, c} = abc and
{1, 2, 3} = {b, a, c} = bac
The above two subsequences of str1
are anagrams of str2.
Input : str1 = "neveropen", str2 = "neveropen"
Output : 48
Approach: Create two arrays freq1[] and freq2[] each of size ’26’ implemented as hash tables to store the frequencies of each character of str1 and str2 respectively. Let n1 and n2 be the lengths of str1 and str2 respectively. Now implement the following algorithm:
countSubsequences(str1, str2)
for i = 0 to n1-1
freq1[str1[i] - 'a']++
for i = 0 n2-1
freq2[str2[i] - 'a']++
Initialize count = 1
for i = 0 to 25
if freq2[i] != 0 then
if freq2[i] <= freq1[i] then
count = count * binomialCoeff(freq1[i], freq2[i])
else
return 0
return count
Let freq1[i] is represented as n and freq2[i] as r. Now, binomialCoeff(n, r) mentioned in the algorithm above is nothing but binomial coefficient nCr .Refer this post for its implementation.
Explanation: Let frequency of some character say ch in ‘str2’ is ‘x’ and in ‘str1’ is ‘y’. If y < x, then no subsequence of ‘str1’ exists which could be an anagram of ‘str2’. Otherwise, yCx gives the number of occurrences of ch selected which will contribute to the total count of required subsequences.
Implementation:
C++
// C++ implementation to// count subsequences in // first string which are // anagrams of the second// string#include <bits/stdc++.h>using namespace std;#define SIZE 26// Returns value of Binomial// Coefficient C(n, k)int binomialCoeff(int n, int k){ int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// function to count subsequences // in first string which are // anagrams of the second stringint countSubsequences(string str1, string str2){ // hash tables to store frequencies // of each character int freq1[SIZE], freq2[SIZE]; int n1 = str1.size(); int n2 = str2.size(); // Initialize memset(freq1, 0, sizeof(freq1)); memset(freq2, 0, sizeof(freq2)); // store frequency of each // character of 'str1' for (int i = 0; i < n1; i++) freq1[str1[i] - 'a']++; // store frequency of each // character of 'str2' for (int i = 0; i < n2; i++) freq2[str2[i] - 'a']++; // to store the total count // of subsequences int count = 1; for (int i = 0; i < SIZE; i++) // if character (i + 'a') // exists in 'str2' if (freq2[i] != 0) { // 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. if (freq2[i] <= freq1[i]) count = count * binomialCoeff(freq1[i], freq2[i]); // else return 0 as there could // be no subsequence which is an // anagram of 'str2' else return 0; } // required count of subsequences return count;}// Driver program to test aboveint main(){ string str1 = "abacd"; string str2 = "abc"; cout << "Count = " << countSubsequences(str1, str2); return 0;} |
Java
// Java implementation to// count subsequences in // first string which are // anagrams of the second// stringimport java.util.*;import java.lang.*;public class GfG{ public final static int SIZE = 26; // Returns value of Binomial // Coefficient C(n, k) public static int binomialCoeff(int n, int k) { int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // function to count subsequences // in first string which are // anagrams of the second string public static int countSubsequences(String str, String str3) { // hash tables to store frequencies // of each character int[] freq1 = new int [SIZE]; int[] freq2 = new int [SIZE]; char[] str1 = str.toCharArray(); char[] str2 = str3.toCharArray(); int n1 = str.length(); int n2 = str3.length(); // store frequency of each // character of 'str1' for (int i = 0; i < n1; i++) freq1[str1[i] - 'a']++; // store frequency of each // character of 'str2' for (int i = 0; i < n2; i++) freq2[str2[i] - 'a']++; // to store the total count // of subsequences int count = 1; for (int i = 0; i < SIZE; i++) // if character (i + 'a') // exists in 'str2' if (freq2[i] != 0) { // 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. if (freq2[i] <= freq1[i]) count = count * binomialCoeff(freq1[i], freq2[i]); // else return 0 as there could // be no subsequence which is an // anagram of 'str2' else return 0; } // required count of subsequences return count; } // Driver function public static void main(String argc[]) { String str1 = "abacd"; String str2 = "abc"; System.out.println("Count = " + countSubsequences(str1, str2)); }}/* This code is contributed by Sagar Shukla */ |
Python
# Python3 implementation to count# subsequences in first which are # anagrams of the second# import libraryimport numpy as npSIZE = 26# Returns value of Binomial# Coefficient C(n, k)def binomialCoeff(n, k): res = 1 # Since C(n, k) = C(n, n-k) if (k > n - k): k = n - k # Calculate value of # [n * (n-1) *---* (n-k+1)] / # [k * (k-1) *----* 1] for i in range(0, k): res = res * (n - i) res = int(res / (i + 1)) return res# Function to count subsequences # in first which are anagrams# of the second def countSubsequences(str1, str2): # Hash tables to store frequencies # of each character freq1 = np.zeros(26, dtype = np.int) freq2 = np.zeros(26, dtype = np.int) n1 = len(str1) n2 = len(str2) # Store frequency of each # character of 'str1' for i in range(0, n1): freq1[ord(str1[i]) - ord('a') ] += 1 # Store frequency of each # character of 'str2' for i in range(0, n2): freq2[ord(str2[i]) - ord('a')] += 1 # To store the total count # of subsequences count = 1 for i in range(0, SIZE): # if character (i + 'a') # exists in 'str2' if (freq2[i] != 0): # 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. if (freq2[i] <= freq1[i]): count = count * binomialCoeff(freq1[i], freq2[i]) # else return 0 as there could # be no subsequence which is an # anagram of 'str2' else: return 0 # required count of subsequences return count# Driver codestr1 = "abacd"str2 = "abc"ans = countSubsequences(str1, str2)print ("Count = ", ans)# This code contributed by saloni1297 |
C#
// C# implementation to// count subsequences in // first string which are // anagrams of the second// stringusing System;class GfG { public static int SIZE = 26; // Returns value of Binomial // Coefficient C(n, k) public static int binomialCoeff(int n, int k) { int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // function to count subsequences // in first string which are // anagrams of the second string public static int countSubsequences(String str, String str3) { // hash tables to store frequencies // of each character int[] freq1 = new int [SIZE]; int[] freq2 = new int [SIZE]; char[] str1 = str.ToCharArray(); char[] str2 = str3.ToCharArray(); int n1 = str.Length; int n2 = str3.Length; // store frequency of each // character of 'str1' for (int i = 0; i < n1; i++) freq1[str1[i] - 'a']++; // store frequency of each // character of 'str2' for (int i = 0; i < n2; i++) freq2[str2[i] - 'a']++; // to store the total count // of subsequences int count = 1; for (int i = 0; i < SIZE; i++) // if character (i + 'a') // exists in 'str2' if (freq2[i] != 0) { // 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. if (freq2[i] <= freq1[i]) count = count * binomialCoeff(freq1[i], freq2[i]); // else return 0 as there could // be no subsequence which is an // anagram of 'str2' else return 0; } // required count of subsequences return count; } // Driver code public static void Main(String[] argc) { String str1 = "abacd"; String str2 = "abc"; Console.Write("Count = " + countSubsequences(str1, str2)); }}// This code is contributed by parashar |
PHP
<?php// PHP implementation to// count subsequences in // first $which are // anagrams of the second// string$SIZE = 26;// Returns value of Binomial// Coefficient C(n, k)function binomialCoeff($n, $k){ $res = 1; // Since C(n, k) = C(n, n-k) if ($k > $n - $k) $k = $n - $k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for ($i = 0; $i < $k; ++$i) { $res *= ($n - $i); $res /= ($i + 1); } return $res;}// function to count // subsequences in // first string which // are anagrams of the// second stringfunction countSubsequences($str1, $str2){ global $SIZE; // hash tables to // store frequencies // of each character $freq1 = array(); $freq2 = array(); // Initialize for ($i = 0; $i < $SIZE; $i++) { $freq1[$i] = 0; $freq2[$i] = 0; } $n1 = strlen($str1); $n2 = strlen($str2); // store frequency of each // character of 'str1' for ($i = 0; $i < $n1; $i++) $freq1[ord($str1[$i]) - ord('a')]++; // store frequency of each // character of 'str2' for ($i = 0; $i < $n2; $i++) $freq2[ord($str2[$i]) - ord('a')]++; // to store the total count // of subsequences $count = 1; for ($i = 0; $i < $SIZE; $i++) // if character (i + 'a') // exists in 'str2' if ($freq2[$i] != 0) { // 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. if ($freq2[$i] <= $freq1[$i]) $count = $count * binomialCoeff($freq1[$i], $freq2[$i]); // else return 0 as there // could be no subsequence // which is an anagram of // 'str2' else return 0; } // required count // of subsequences return $count;}// Driver Code$str1 = "abacd";$str2 = "abc";echo ("Count = ". countSubsequences($str1, $str2));// This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script>// JavaScript implementation to// count subsequences in // first string which are // anagrams of the second// stringvar SIZE = 26// Returns value of Binomial// Coefficient C(n, k)function binomialCoeff(n, k){ var res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n * (n-1) *---* (n-k+1)] / // [k * (k-1) *----* 1] for (var i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// function to count subsequences // in first string which are // anagrams of the second stringfunction countSubsequences(str1, str2){ // hash tables to store frequencies // of each character var freq1 = Array(SIZE).fill(0), freq2 = Array(SIZE).fill(0); var n1 = str1.length; var n2 = str2.length; // store frequency of each // character of 'str1' for (var i = 0; i < n1; i++) freq1[str1[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; // store frequency of each // character of 'str2' for (var i = 0; i < n2; i++) freq2[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; // to store the total count // of subsequences var count = 1; for (var i = 0; i < SIZE; i++) // if character (i + 'a') // exists in 'str2' if (freq2[i] != 0) { // 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. if (freq2[i] <= freq1[i]) count = count * binomialCoeff(freq1[i], freq2[i]); // else return 0 as there could // be no subsequence which is an // anagram of 'str2' else return 0; } // required count of subsequences return count;}// Driver program to test abovevar str1 = "abacd";var str2 = "abc";document.write( "Count = " + countSubsequences(str1, str2));</script> |
Output
Count = 2
Time Complexity: O(n1 + n2) + O(max), where n1 and n2 are the lengths of the input strings and max is the maximum frequency.
Auxiliary space: O(26). The algorithm uses two integer arrays of size 26 to store the frequency of characters in both strings, which takes O(26) space. Also, it uses some constant extra space to store some variables. Therefore, the overall space complexity of the algorithm is O(1).
This article is contributed by Aarti_Rathi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
