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 = “neveropen”, patt = “neveropen”
Output: 2
“neveropen” can be made at most twice from
the characters of “neveropen”.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 = "neveropen" ; string patt = "neveropen" ; 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 = "neveropen" ; String patt = "neveropen" ; 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 = "neveropen" patt = "neveropen" 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 = "neveropen" ; String patt = "neveropen" ; 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 = "neveropen" ; var patt = "neveropen" ; 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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!