Count occurrences of a string that can be constructed from another given string

0 0 4 minutes read

Given two strings str1 and str2 where str1 being the parent string. The task is to find out the number of string as str2 that can be constructed using letters of str1.

Note: All the letters are in lowercase and each character should be used only once.

Examples:

Input: str1 = "zambiatek", str2 = "zambiatek"
Output: 2

Input: str1 = "geekgoinggeeky", str2 = "zambiatek"
Output: 0

Approach: Store the frequency of characters of str2 in hash2, and do the same for str1 in hash1. Now, find out the minimum value of hash1[i]/hash2[i] for all i where hash2[i]>0.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count
int findCount(string str1, string str2)
{
    int len = str1.size();
    int len2 = str2.size();
    int ans = INT_MAX;
 
    // Initialize hash for both strings
    int hash1[26] = { 0 }, hash2[26] = { 0 };
 
    // hash the frequency of letters of str1
    for (int i = 0; i < len; i++)
        hash1[str1[i] - 'a']++;
 
    // hash the frequency of letters of str2
    for (int i = 0; i < len2; i++)
        hash2[str2[i] - 'a']++;
 
    // Find the count of str2 constructed from str1
    for (int i = 0; i < 26; i++)
        if (hash2[i])
            ans = min(ans, hash1[i] / hash2[i]);
 
    // Return answer
    return ans;
}
 
// Driver code
int main()
{
    string str1 = "zambiatekclassesatnoida";
    string str2 = "sea";
    cout << findCount(str1, str2);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.io.*;
public class GFG
{
    // Function to find the count
    static int findCount(String str1, String str2)
    {
        int len = str1.length();
        int len2 = str2.length();
        int ans = Integer.MAX_VALUE;
     
        // Initialize hash for both strings
        int [] hash1 = new int[26];
        int [] hash2 = new int[26];
     
        // hash the frequency of letters of str1
        for (int i = 0; i < len; i++)
            hash1[(int)(str1.charAt(i) - 'a')]++;
     
        // hash the frequency of letters of str2
        for (int i = 0; i < len2; i++)
            hash2[(int)(str2.charAt(i) - 'a')]++;
     
        // Find the count of str2 constructed from str1
        for (int i = 0; i < 26; i++)
            if (hash2[i] != 0)
                ans = Math.min(ans, hash1[i] / hash2[i]);
     
        // Return answer
        return ans;
    }
     
    // Driver code
    public static void main(String []args)
    {
        String str1 = "zambiatekclassesatnoida";
        String str2 = "sea";
        System.out.println(findCount(str1, str2));
    }
}
 
// This code is contributed by ihritik

Python3

# Python3 implementation of the above approach
 
import sys
 
# Function to find the count
def findCount(str1, str2):
 
    len1 = len(str1)
    len2 = len(str2)
    ans = sys.maxsize
 
    # Initialize hash for both strings
    hash1 = [0] * 26
    hash2 = [0] * 26
 
    # hash the frequency of letters of str1
    for i in range(0, len1):
        hash1[ord(str1[i]) - 97] = hash1[ord(str1[i]) - 97] + 1
 
    # hash the frequency of letters of str2
    for i in range(0, len2):
        hash2[ord(str2[i]) - 97] = hash2[ord(str2[i]) - 97] + 1
         
    # Find the count of str2 constructed from str1
    for i in range (0, 26):
        if (hash2[i] != 0):
            ans = min(ans, hash1[i] // hash2[i])
 
    # Return answer
    return ans
 
     
# Driver code
str1 = "zambiatekclassesatnoida"
str2 = "sea"
print(findCount(str1, str2))
 
# This code is contributed by ihritik

C#

// C# implementation of the above approach
using System;
 
class GFG
{
    // Function to find the count
    static int findCount(string str1, string str2)
    {
        int len = str1.Length;
        int len2 = str2.Length;
        int ans = Int32.MaxValue;
     
        // Initialize hash for both strings
        int [] hash1 = new int[26];
        int [] hash2 = new int[26];
     
        // hash the frequency of letters of str1
        for (int i = 0; i < len; i++)
            hash1[str1[i] - 'a']++;
     
        // hash the frequency of letters of str2
        for (int i = 0; i < len2; i++)
            hash2[str2[i] - 'a']++;
     
        // Find the count of str2 constructed from str1
        for (int i = 0; i < 26; i++)
            if (hash2[i] != 0)
                ans = Math.Min(ans, hash1[i] / hash2[i]);
     
        // Return answer
        return ans;
    }
     
    // Driver code
    public static void Main()
    {
        string str1 = "zambiatekclassesatnoida";
        string str2 = "sea";
        Console.WriteLine(findCount(str1, str2));
    }
}
 
// This code is contributed by ihritik

PHP

<?php
// PHP implementation of the above approach 
 
// Function to find the count 
function findCount($str1, $str2) 
{ 
    $len = strlen($str1) ; 
    $len2 = strlen($str1); 
    $ans = PHP_INT_MAX; 
 
    // Initialize hash for both strings 
    $hash1 = array_fill(0, 26, 0) ;
    $hash2 = array_fill(0, 26, 0); 
 
    // hash the frequency of letters of str1 
    for ($i = 0; $i < $len; $i++) 
        $hash1[ord($str1[$i]) - ord('a')]++; 
 
    // hash the frequency of letters of str2 
    for ($i = 0; $i < $len2; $i++) 
        $hash2[ord($str2[$i]) - ord('a')]++; 
 
    // Find the count of str2 constructed from str1 
    for ($i = 0; $i < 26; $i++) 
        if ($hash2[$i]) 
            $ans = min($ans, $hash1[$i] / $hash2[$i]); 
 
    // Return answer 
    return $ans; 
} 
 
    // Driver code 
    $str1 = "zambiatekclassesatnoida"; 
    $str2 = "sea"; 
    echo findCount($str1, $str2); 
     
// This code is contributed by Ryuga
?>

Javascript

<script>
      // JavaScript implementation of the above approach
 
      // Function to find the count
      function findCount(str1, str2) {
        var len = str1.length;
        var len2 = str2.length;
        //MAX Integer Value
        var ans = 21474836473;
 
        // Initialize hash for both strings
        var hash1 = new Array(26).fill(0);
        var hash2 = new Array(26).fill(0);
 
        // hash the frequency of letters of str1
        for (var i = 0; i < len; i++)
          hash1[str1[i].charCodeAt(0) - "a".charCodeAt(0)]++;
 
        // hash the frequency of letters of str2
        for (var i = 0; i < len2; i++)
          hash2[str2[i].charCodeAt(0) - "a".charCodeAt(0)]++;
 
        // Find the count of str2 constructed from str1
        for (var i = 0; i < 26; i++)
          if (hash2[i]) ans = Math.min(ans, hash1[i] / hash2[i]);
 
        // Return answer
        return ans;
      }
 
      // Driver code
      var str1 = "zambiatekclassesatnoida";
      var str2 = "sea";
      document.write(findCount(str1, str2));
    </script>

Output

Complexity Analysis:

Time Complexity: O(n)
Auxiliary Space: O(1)

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 zambiatek!