Número máximo de veces que str1 aparece como una substring que no se superpone en str2

Dadas dos strings str1 y str2 , la tarea es encontrar el número máximo de veces que str1 aparece en str2 como una substring que no se superpone después de reorganizar los caracteres de str2
Ejemplos: 
 

Entrada: str1 = «geeks», str2 = «gskefrgoekees» 
Salida: 2 
str = » geeks for geeks »
Entrada: str1 = «aa», str2 = «aaaa» 
Salida: 2 
 

Enfoque: La idea es almacenar la frecuencia de caracteres de ambas strings y compararlas. 
 

• Si hay un carácter cuya frecuencia en la primera string es mayor que su frecuencia en la segunda string, la respuesta siempre es 0 porque la string str1 nunca puede aparecer en str2 .
• Después de almacenar la frecuencia de los caracteres de ambas strings, realice una división entera entre la frecuencia distinta de cero de los caracteres de str1 y str2 . El valor mínimo sería la respuesta.

A continuación se muestra la implementación del enfoque anterior: 
 

// 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 = "geeks", str2 = "gskefrgoekees";
    int len1 = str1.length();
    int len2 = str2.length();
 
    cout << maxSubStr(str1, len1, str2, len2);
 
    return 0;
}

// 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 = "geeks", 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 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 = "geeks"; str2 = "gskefrgoekees";
len1 = len(str1);
len2 = len(str2);
 
print(maxSubStr(str1, len1, str2, len2));
 
# This code is contributed by 29AjayKumar

// 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 = "geeks", 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

<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 = "geeks", 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>

2

Complejidad de tiempo: O (max (M, N)), ya que usamos un bucle para atravesar N veces y M veces. Donde M y N son las longitudes de las strings dadas str1 y str2 respectivamente.
Espacio auxiliar: O(26), ya que estamos usando espacio extra para el mapa.