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 strvoid 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 strint 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 codeint main(){ string str = "neveropen"; string patt = "neveropen"; cout << maxCount(str, patt); return 0;} |
Java
// Java implementation of the approachclass GFG{static int MAX = 26;// Function to update the freq[] array// to store the frequencies of// all the characters of strstatic 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 strstatic 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 codepublic 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 approachMAX = 26# Function to update the freq[] array# to store the frequencies of# all the characters of strrdef 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 strrdef 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 codestrr = "neveropen"patt = "neveropen"print(maxCount(strr, patt))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{static int MAX = 26;// Function to update the []freq array// to store the frequencies of// all the characters of strstatic 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 strstatic 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 codepublic 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> |
Output:
2
Time Complexity: O(m+n) where m and n are lengths of the given string str and patt respectively.
Auxiliary Space: O(MAX)
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!
