Maximum number of times str1 appears as a non-overlapping substring in str2
Given two strings str1 and str2, the task is to find the maximum number of times str1 occurs in str2 as a non-overlapping substring after rearranging the characters of str2
Examples:
Input: str1 = “Beginner”, str2 = “gskefrgoekees”
Output: 2
str = “BeginnerforBeginner“
Input: str1 = “aa”, str2 = “aaaa”
Output: 2
Approach: The idea is to store the frequency of characters of both the strings and comparing them.
- If there is a character whose frequency in the first string is greater than its frequency in the second string then the answer is always 0 because string str1 can never occur in str2.
- After storing the frequency of the characters of both the strings, perform integer division between the non-zero frequency of characters of str1 and str2. The minimum value would be the 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 return the maximum number // of times str1 can appear as a // non-overlapping substring in str2 int maxSubStr(string str1, int len1, string str2, int len2) { // str1 cannot never be substring of str2 if (len1 > len2) return 0; // Store the frequency of the characters of str1 int freq1[MAX] = { 0 }; for ( int i = 0; i < len1; i++) freq1[str1[i] - 'a' ]++; // Store the frequency of the characters of str2 int freq2[MAX] = { 0 }; for ( int i = 0; i < len2; i++) freq2[str2[i] - 'a' ]++; // To store the required count of substrings int minPoss = INT_MAX; for ( int i = 0; i < MAX; i++) { // Current character doesn't appear in str1 if (freq1[i] == 0) continue ; // Frequency of the current character in str1 // is greater than its frequency in str2 if (freq1[i] > freq2[i]) return 0; // Update the count of possible substrings minPoss = min(minPoss, freq2[i] / freq1[i]); } return minPoss; } // Driver code int main() { string str1 = "Beginner" , str2 = "gskefrgoekees" ; int len1 = str1.length(); int len2 = str2.length(); cout << maxSubStr(str1, len1, str2, len2); return 0; } |
Java
// Java implementation of the approach class GFG { final static int MAX = 26 ; // Function to return the maximum number // of times str1 can appear as a // non-overlapping substring in str2 static int maxSubStr( char []str1, int len1, char []str2, int len2) { // str1 cannot never be substring of str2 if (len1 > len2) return 0 ; // Store the frequency of the characters of str1 int freq1[] = new int [MAX]; for ( int i = 0 ; i < len1; i++) freq1[i] = 0 ; for ( int i = 0 ; i < len1; i++) freq1[str1[i] - 'a' ]++; // Store the frequency of the characters of str2 int freq2[] = new int [MAX]; for ( int i = 0 ; i < len2; i++) freq2[i] = 0 ; for ( int i = 0 ; i < len2; i++) freq2[str2[i] - 'a' ]++; // To store the required count of substrings int minPoss = Integer.MAX_VALUE; for ( int i = 0 ; i < MAX; i++) { // Current character doesn't appear in str1 if (freq1[i] == 0 ) continue ; // Frequency of the current character in str1 // is greater than its frequency in str2 if (freq1[i] > freq2[i]) return 0 ; // Update the count of possible substrings minPoss = Math.min(minPoss, freq2[i] / freq1[i]); } return minPoss; } // Driver code public static void main (String[] args) { String str1 = "Beginner" , str2 = "gskefrgoekees" ; int len1 = str1.length(); int len2 = str2.length(); System.out.println(maxSubStr(str1.toCharArray(), len1, str2.toCharArray(), len2)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach import sys MAX = 26 ; # Function to return the maximum number # of times str1 can appear as a # non-overlapping substring bin str2 def maxSubStr(str1, len1, str2, len2): # str1 cannot never be # substring of str2 if (len1 > len2): return 0 ; # Store the frequency of # the characters of str1 freq1 = [ 0 ] * MAX ; for i in range (len1): freq1[ ord (str1[i]) - ord ( 'a' )] + = 1 ; # Store the frequency of # the characters of str2 freq2 = [ 0 ] * MAX ; for i in range (len2): freq2[ ord (str2[i]) - ord ( 'a' )] + = 1 ; # To store the required count # of substrings minPoss = sys.maxsize; for i in range ( MAX ): # Current character doesn't appear # in str1 if (freq1[i] = = 0 ): continue ; # Frequency of the current character # in str1 is greater than its # frequency in str2 if (freq1[i] > freq2[i]): return 0 ; # Update the count of possible substrings minPoss = min (minPoss, freq2[i] / freq1[i]); return int (minPoss); # Driver code str1 = "Beginner" ; str2 = "gskefrgoekees" ; len1 = len (str1); len2 = len (str2); print (maxSubStr(str1, len1, str2, len2)); # This code is contributed by 29AjayKumar |
C#
// C# implementation of the above approach using System; class GFG { readonly static int MAX = 26; // Function to return the maximum number // of times str1 can appear as a // non-overlapping substring in str2 static int maxSubStr( char []str1, int len1, char []str2, int len2) { // str1 cannot never be substring of str2 if (len1 > len2) return 0; // Store the frequency of the characters of str1 int []freq1 = new int [MAX]; for ( int i = 0; i < len1; i++) freq1[i] = 0; for ( int i = 0; i < len1; i++) freq1[str1[i] - 'a' ]++; // Store the frequency of the characters of str2 int []freq2 = new int [MAX]; for ( int i = 0; i < len2; i++) freq2[i] = 0; for ( int i = 0; i < len2; i++) freq2[str2[i] - 'a' ]++; // To store the required count of substrings int minPoss = int .MaxValue; for ( int i = 0; i < MAX; i++) { // Current character doesn't appear in str1 if (freq1[i] == 0) continue ; // Frequency of the current character in str1 // is greater than its frequency in str2 if (freq1[i] > freq2[i]) return 0; // Update the count of possible substrings minPoss = Math.Min(minPoss, freq2[i] / freq1[i]); } return minPoss; } // Driver code public static void Main (String[] args) { String str1 = "Beginner" , str2 = "gskefrgoekees" ; int len1 = str1.Length; int len2 = str2.Length; Console.WriteLine(maxSubStr(str1.ToCharArray(), len1, str2.ToCharArray(), len2)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach const MAX = 26; // Function to return the maximum number // of times str1 can appear as a // non-overlapping substring in str2 function maxSubStr(str1, len1, str2, len2) { // str1 cannot never be substring of str2 if (len1 > len2) return 0; // Store the frequency of the characters of str1 let freq1 = new Array(MAX).fill(0); for (let i = 0; i < len1; i++) freq1[str1.charCodeAt(i) - 'a' .charCodeAt(0)]++; // Store the frequency of the characters of str2 let freq2 = new Array(MAX).fill(0); for (let i = 0; i < len2; i++) freq2[str2.charCodeAt(i) - 'a' .charCodeAt(0)]++; // To store the required count of substrings let minPoss = Number.MAX_SAFE_INTEGER; for (let i = 0; i < MAX; i++) { // Current character doesn't appear in str1 if (freq1[i] == 0) continue ; // Frequency of the current character in str1 // is greater than its frequency in str2 if (freq1[i] > freq2[i]) return 0; // Update the count of possible substrings minPoss = Math.min(minPoss, Math.floor(freq2[i] / freq1[i])); } return minPoss; } // Driver code let str1 = "Beginner" , str2 = "gskefrgoekees" ; let len1 = str1.length; let len2 = str2.length; document.write(maxSubStr(str1, len1, str2, len2)); // This code is contributed by _saurabh_jaiswal. </script> |
Output:
2
Time Complexity: O(max(M, N)), as we using a loop to traverse N times and M times. Where M and N are the lengths of the given strings str1 and str2 respectively.
Auxiliary Space: O(26), as we are using extra space for the map.
Contact Us