Count of times second string can be formed from the characters of first string
Given two strings str and patt, the task is to find the count of times patt can be formed using the characters of str.
Examples:
Input: str = “w3wiki”, patt = “Beginner”
Output: 2
“Beginner” can be made at most twice from
the characters of “w3wiki”.Input: str = “abcbca”, patt = “aabc”
Output: 1
Approach: Count the frequency of all the characters of str and patt and store them in arrays strFreq[] and pattFreq[] respectively. Now any character ch which appears in patt can be used in a maximum of strFreq[ch] / pattFreq[ch] words and the minimum of this value among all the characters of patt is the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; const int MAX = 26; // Function to update the freq[] array // to store the frequencies of // all the characters of str void updateFreq(string str, int freq[]) { int len = str.length(); // Update the frequency of the characters for ( int i = 0; i < len; i++) { freq[str[i] - 'a' ]++; } } // Function to return the maximum count // of times patt can be formed // using the characters of str int maxCount(string str, string patt) { // To store the frequencies of // all the characters of str int strFreq[MAX] = { 0 }; updateFreq(str, strFreq); // To store the frequencies of // all the characters of patt int pattFreq[MAX] = { 0 }; updateFreq(patt, pattFreq); // To store the result int ans = INT_MAX; // For every character for ( int i = 0; i < MAX; i++) { // If the current character // doesn't appear in patt if (pattFreq[i] == 0) continue ; // Update the result ans = min(ans, strFreq[i] / pattFreq[i]); } return ans; } // Driver code int main() { string str = "w3wiki" ; string patt = "Beginner" ; cout << maxCount(str, patt); return 0; } |
Java
// Java implementation of the approach class GFG { static int MAX = 26 ; // Function to update the freq[] array // to store the frequencies of // all the characters of str static void updateFreq(String str, int freq[]) { int len = str.length(); // Update the frequency of the characters for ( int i = 0 ; i < len; i++) { freq[str.charAt(i) - 'a' ]++; } } // Function to return the maximum count // of times patt can be formed // using the characters of str static int maxCount(String str, String patt) { // To store the frequencies of // all the characters of str int []strFreq = new int [MAX]; updateFreq(str, strFreq); // To store the frequencies of // all the characters of patt int []pattFreq = new int [MAX]; updateFreq(patt, pattFreq); // To store the result int ans = Integer.MAX_VALUE; // For every character for ( int i = 0 ; i < MAX; i++) { // If the current character // doesn't appear in patt if (pattFreq[i] == 0 ) continue ; // Update the result ans = Math.min(ans, strFreq[i] / pattFreq[i]); } return ans; } // Driver code public static void main(String[] args) { String str = "w3wiki" ; String patt = "Beginner" ; System.out.print(maxCount(str, patt)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach MAX = 26 # Function to update the freq[] array # to store the frequencies of # all the characters of strr def updateFreq(strr, freq): lenn = len (strr) # Update the frequency of the characters for i in range (lenn): freq[ ord (strr[i]) - ord ( 'a' )] + = 1 # Function to return the maximum count # of times patt can be formed # using the characters of strr def maxCount(strr, patt): # To store the frequencies of # all the characters of strr strrFreq = [ 0 for i in range ( MAX )] updateFreq(strr, strrFreq) # To store the frequencies of # all the characters of patt pattFreq = [ 0 for i in range ( MAX )] updateFreq(patt, pattFreq) # To store the result ans = 10 * * 9 # For every character for i in range ( MAX ): # If the current character # doesn't appear in patt if (pattFreq[i] = = 0 ): continue # Update the result ans = min (ans, strrFreq[i] / / pattFreq[i]) return ans # Driver code strr = "w3wiki" patt = "Beginner" print (maxCount(strr, patt)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 26; // Function to update the []freq array // to store the frequencies of // all the characters of str static void updateFreq(String str, int []freq) { int len = str.Length; // Update the frequency of the characters for ( int i = 0; i < len; i++) { freq[str[i] - 'a' ]++; } } // Function to return the maximum count // of times patt can be formed // using the characters of str static int maxCount(String str, String patt) { // To store the frequencies of // all the characters of str int []strFreq = new int [MAX]; updateFreq(str, strFreq); // To store the frequencies of // all the characters of patt int []pattFreq = new int [MAX]; updateFreq(patt, pattFreq); // To store the result int ans = int .MaxValue; // For every character for ( int i = 0; i < MAX; i++) { // If the current character // doesn't appear in patt if (pattFreq[i] == 0) continue ; // Update the result ans = Math.Min(ans, strFreq[i] / pattFreq[i]); } return ans; } // Driver code public static void Main(String[] args) { String str = "w3wiki" ; String patt = "Beginner" ; Console.Write(maxCount(str, patt)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the approach const MAX = 26; // Function to update the freq[] array // to store the frequencies of // all the characters of str function updateFreq(str, freq) { var len = str.length; // Update the frequency of the characters for ( var i = 0; i < len; i++) { freq[str[i].charCodeAt(0) - "a" .charCodeAt(0)]++; } } // Function to return the maximum count // of times patt can be formed // using the characters of str function maxCount(str, patt) { // To store the frequencies of // all the characters of str var strFreq = new Array(MAX).fill(0); updateFreq(str, strFreq); // To store the frequencies of // all the characters of patt var pattFreq = new Array(MAX).fill(0); updateFreq(patt, pattFreq); // To store the result var ans = 21474836473; // For every character for ( var i = 0; i < MAX; i++) { // If the current character // doesn't appear in patt if (pattFreq[i] == 0) continue ; // Update the result ans = Math.min(ans, strFreq[i] / pattFreq[i]); } return ans; } // Driver code var str = "w3wiki" ; var patt = "Beginner" ; document.write(maxCount(str, patt)); </script> |
2
Time Complexity: O(m+n) where m and n are lengths of the given string str and patt respectively.
Auxiliary Space: O(MAX)