La substring más grande donde todos los caracteres aparecen al menos K veces

Dada una string str y un entero K , la tarea es encontrar la longitud de la substring más larga S’ tal que cada carácter en S’ aparezca al menos K veces.
 

Entrada: s = “xyxyyz”, k = 2 
Salida: 5 
“xyxyy” es la substring más larga donde 
cada carácter aparece al menos dos veces.
Entrada: s = «geeksforgeeks», k = 2 
Salida: 2 
 

Enfoque: considere todas las substrings posibles y, para cada substring, calcule la frecuencia de cada uno de sus caracteres y verifique si todos los caracteres aparecen al menos K veces. Para todas esas substrings válidas, encuentre la mayor longitud posible.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 26
 
// Function that return true if frequency
// of all the present characters is at least k
bool atLeastK(int freq[], int k)
{
    for (int i = 0; i < MAX; i++) {
 
        // If the character is present and
        // its frequency is less than k
        if (freq[i] != 0 && freq[i] < k)
            return false;
    }
 
    return true;
}
 
// Function to set every frequency to zero
void setZero(int freq[])
{
    for (int i = 0; i < MAX; i++)
        freq[i] = 0;
}
 
// Function to return the length of the longest
// sub-string such that it contains every
// character at least k times
int findlength(string str, int n, int k)
{
 
    // To store the required maximum length
    int maxLen = 0;
 
    int freq[MAX];
 
    // Starting index of the sub-string
    for (int i = 0; i < n; i++) {
        setZero(freq);
 
        // Ending index of the sub-string
        for (int j = i; j < n; j++) {
            freq[str[j] - 'a']++;
 
            // If the frequency of every character
            // of the current sub-string is at least k
            if (atLeastK(freq, k)) {
 
                // Update the maximum possible length
                maxLen = max(maxLen, j - i + 1);
            }
        }
    }
 
    return maxLen;
}
 
// Driver code
int main()
{
    string str = "xyxyyz";
    int n = str.length();
    int k = 2;
 
    cout << findlength(str, n, k);
 
    return 0;
}

// Java Implementation of the above approach
class GFG
{
 
static final int MAX = 26;
 
// Function that return true if frequency
// of all the present characters is at least k
static boolean atLeastK(int freq[], int k)
{
    for (int i = 0; i < MAX; i++)
    {
 
        // If the character is present and
        // its frequency is less than k
        if (freq[i] != 0 && freq[i] < k)
            return false;
    }
 
    return true;
}
 
// Function to set every frequency to zero
static void setZero(int freq[])
{
    for (int i = 0; i < MAX; i++)
        freq[i] = 0;
}
 
// Function to return the length of the longest
// sub-string such that it contains every
// character at least k times
static int findlength(String str, int n, int k)
{
 
    // To store the required maximum length
    int maxLen = 0;
 
    int freq[] = new int[MAX];
 
    // Starting index of the sub-string
    for (int i = 0; i < n; i++)
    {
        setZero(freq);
 
        // Ending index of the sub-string
        for (int j = i; j < n; j++)
        {
            freq[str.charAt(j) - 'a']++;
 
            // If the frequency of every character
            // of the current sub-string is at least k
            if (atLeastK(freq, k))
            {
 
                // Update the maximum possible length
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
 
    return maxLen;
}
 
// Driver code
public static void main(String args[])
{
    String str = "xyxyyz";
    int n = str.length();
    int k = 2;
 
    System.out.println(findlength(str, n, k));
 
}
}
 
// This code has been contributed by 29AjayKumar

# Python3 implementation of the approach
MAX = 26
 
# Function that return true if frequency
# of all the present characters is at least k
def atLeastK(freq, k) :
 
    for i in range(MAX) :
 
        # If the character is present and
        # its frequency is less than k
        if (freq[i] != 0 and freq[i] < k) :
            return False;
     
    return True;
 
 
# Function to set every frequency to zero
def setZero(freq) :
 
    for i in range(MAX) :
        freq[i] = 0;
 
 
# Function to return the length of the longest
# sub-string such that it contains every
# character at least k times
def findlength(string, n, k) :
 
    # To store the required maximum length
    maxLen = 0;
 
    freq = [0]*MAX;
 
    # Starting index of the sub-string
    for i in range(n) :
        setZero(freq);
 
        # Ending index of the sub-string
        for j in range(i,n) :
            freq[ord(string[j]) - ord('a')] += 1;
 
            # If the frequency of every character
            # of the current sub-string is at least k
            if (atLeastK(freq, k)) :
 
                # Update the maximum possible length
                maxLen = max(maxLen, j - i + 1);
         
    return maxLen;
 
 
# Driver code
if __name__ == "__main__" :
 
    string = "xyxyyz";
    n = len(string);
    k = 2;
 
    print(findlength(string, n, k));
     
# This code is contributed by AnkitRai01

// C# Implementation of the above approach
using System;
     
class GFG
{
 
static int MAX = 26;
 
// Function that return true if frequency
// of all the present characters is at least k
static Boolean atLeastK(int []freq, int k)
{
    for (int i = 0; i < MAX; i++)
    {
 
        // If the character is present and
        // its frequency is less than k
        if (freq[i] != 0 && freq[i] < k)
            return false;
    }
 
    return true;
}
 
// Function to set every frequency to zero
static void setZero(int []freq)
{
    for (int i = 0; i < MAX; i++)
        freq[i] = 0;
}
 
// Function to return the length of the longest
// sub-string such that it contains every
// character at least k times
static int findlength(String str, int n, int k)
{
 
    // To store the required maximum length
    int maxLen = 0;
 
    int []freq = new int[MAX];
 
    // Starting index of the sub-string
    for (int i = 0; i < n; i++)
    {
        setZero(freq);
 
        // Ending index of the sub-string
        for (int j = i; j < n; j++)
        {
            freq[str[j] - 'a']++;
 
            // If the frequency of every character
            // of the current sub-string is at least k
            if (atLeastK(freq, k))
            {
 
                // Update the maximum possible length
                maxLen = Math.Max(maxLen, j - i + 1);
            }
        }
    }
 
    return maxLen;
}
 
// Driver code
public static void Main(String []args)
{
    String str = "xyxyyz";
    int n = str.Length;
    int k = 2;
 
    Console.WriteLine(findlength(str, n, k));
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript implementation of the approach
 
var MAX = 26;
 
// Function that return true if frequency
// of all the present characters is at least k
function atLeastK(freq, k)
{
    for (var i = 0; i < MAX; i++) {
 
        // If the character is present and
        // its frequency is less than k
        if (freq[i] != 0 && freq[i] < k)
            return false;
    }
 
    return true;
}
 
// Function to set every frequency to zero
function setZero(freq)
{
    for (var i = 0; i < MAX; i++)
        freq[i] = 0;
}
 
// Function to return the length of the longest
// sub-string such that it contains every
// character at least k times
function findlength(str, n, k)
{
 
    // To store the required maximum length
    var maxLen = 0;
 
    var freq = Array(MAX).fill(0);
 
    // Starting index of the sub-string
    for (var i = 0; i < n; i++) {
        setZero(freq);
 
        // Ending index of the sub-string
        for (var j = i; j < n; j++) {
            freq[str[j].charCodeAt(0) - 'a'.charCodeAt(0)]++;
 
            // If the frequency of every character
            // of the current sub-string is at least k
            if (atLeastK(freq, k)) {
 
                // Update the maximum possible length
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
 
    return maxLen;
}
 
// Driver code
var str = "xyxyyz";
var n = str.length;
var k = 2;
document.write( findlength(str, n, k));
 
</script>

5

Complejidad de tiempo: O(n ² )
Espacio auxiliar: O(MAX), donde MAX es el número máximo de caracteres únicos en la string.