Substring más grande donde todos los caracteres aparecen al menos K veces | conjunto 2

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

Ejemplos:

Entrada: str = “aabbba”, K = 3
Salida: 6 
Explicación: 
En la substring aabbba, cada carácter se repite al menos k veces y su longitud es 6.

Entrada: str = “ababacb”, K = 3
Salida: 0 
Explicación: 
No hay una substring donde cada carácter se repita al menos k veces.

Enfoque ingenuo: Hemos discutido el enfoque ingenuo en la publicación anterior . 

Enfoque: En esta publicación, discutiremos el enfoque utilizando la técnica Divide and Conquer y Recursion . A continuación se muestran los pasos:

1. Almacene la frecuencia de cada carácter de la string dada en una array de frecuencia de tamaño 26 .
2. Inicializa dos variables que comienzan con 0 y terminan , que es la longitud de la string str .
3. Repita la string de principio a fin y cuente la cantidad de veces que se repite cada carácter y guárdelo en una array.
4. Si algún carácter se repite menos de K veces , divida la string en dos mitades. Si i es el índice de la string donde encontramos que la string[i] se repite menos de K veces , entonces dividimos la string en dos mitades desde el inicio hasta la i y i + 1 hasta el final .
5. Invoque recursivamente las dos mitades en los pasos anteriores, es decir, desde el inicio hasta i e i + 1 para terminar por separado y repita los pasos 2 y 3 y devuelva el máximo de los dos valores devueltos por la llamada recursiva anterior.
6. Si todos los caracteres entre el inicio y el final se repiten al menos K veces, entonces la respuesta es final – inicio .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest substring
int longestSubstring(int start, int end,
                    string s, int k)
{
    int left, right;
 
    // Array for counting the number of
    // times each character repeats
    // count the number of times each
    // character repeats from start to end
    int count[26] = { 0 };
 
    // Store the frequency from s[start...end]
    for (int i = start; i < end; i++) {
        count[s[i] - 'a'] += 1;
    }
 
    // Iterate from [start, end]
    for (int i = start; i < end; i++) {
 
        if (count[s[i] - 'a'] < k) {
 
            // Recursive call for left subpart
            left = longestSubstring(start,
                                    i,
                                    s,
                                    k);
 
            // Recursive call for right subpart
            right = longestSubstring(i + 1,
                                    end,
                                    s,
                                    k);
 
            // Return maximum of left & right
            return max(left, right);
        }
    }
 
    // If all the characters are repeated
    // at least k times
    return end - start;
}
 
// Driver Code
int main()
{
    // Given String str
    string str = "aabbba";
    int k = 3;
 
    // Function Call
    cout << longestSubstring(0, str.length(),
                            str, k)
        << endl;
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the longest subString
static int longestSubString(int start, int end,
                            String s, int k)
{
    int left, right;
 
    // Array for counting the number of
    // times each character repeats
    // count the number of times each
    // character repeats from start to end
    int count[] = new int[26];
 
    // Store the frequency from s[start...end]
    for(int i = start; i < end; i++)
    {
        count[s.charAt(i) - 'a'] += 1;
    }
 
    // Iterate from [start, end]
    for(int i = start; i < end; i++)
    {
        if (count[s.charAt(i) - 'a'] < k)
        {
             
            // Recursive call for left subpart
            left = longestSubString(start, i,
                                    s, k);
 
            // Recursive call for right subpart
            right = longestSubString(i + 1, end,
                                    s, k);
 
            // Return maximum of left & right
            return Math.max(left, right);
        }
    }
 
    // If all the characters are repeated
    // at least k times
    return end - start;
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given String str
    String str = "aabbba";
    int k = 3;
 
    // Function Call
    System.out.print(longestSubString(0, str.length(),
                                        str, k) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to find the longest substring
def longestSubString(start, end, s, k):
     
    # List for counting the number of
    # times each character repeats
    # count the number of times each
    # character repeats from start to end
    count = [0 for i in range(26)]
     
    # Store the frequency from s[start...end]
    for i in range(start, end):
        count[ord(s[i]) - ord('a')] += 1
     
    # Iterate from [start, end]
    for i in range(start, end):
        if(count[ ord(s[i]) - ord('a')] < k):
             
            # Recursive call for left subpart
            left = longestSubString(start, i,
                                        s, k)
                                     
            # Recursive call for right subpart
            right = longestSubString(i + 1, end,
                                        s, k)
                                     
            # Return maximum of left & right
            return max(left, right)
     
    # If all the characters are repeated
    # at least k times
    return end - start
     
# Driver Code
 
# Given String str
str = "aabbba"
k = 3
 
# Function call
print(longestSubString(0, len(str), str, k))
 
# This code is contributed by dadimadhav

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the longest subString
static int longestSubString(int start, int end,
                             string s, int k)
{
    int left, right;
 
    // Array for counting the number of
    // times each character repeats
    // count the number of times each
    // character repeats from start to end
    int []count = new int[26];
 
    // Store the frequency from s[start...end]
    for(int i = start; i < end; i++)
    {
        count[s[i] - 'a'] += 1;
    }
 
    // Iterate from [start, end]
    for(int i = start; i < end; i++)
    {
        if (count[s[i] - 'a'] < k)
        {
             
            // Recursive call for left subpart
            left = longestSubString(start, i,
                                    s, k);
 
            // Recursive call for right subpart
            right = longestSubString(i + 1, end,
                                     s, k);
 
            // Return maximum of left & right
            return Math.Max(left, right);
        }
    }
 
    // If all the characters are repeated
    // at least k times
    return end - start;
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given String str
    string str = "aabbba";
    int k = 3;
 
    // Function call
    Console.Write(longestSubString(0, str.Length,
                                      str, k) + "\n");
}
}
 
// This code is contributed by rutvik_56

<script>
 
// JavaScript program for the above approach
// Function to find the longest subString
function longestSubString(start, end, s, k)
{
    var left, right;
 
    // Array for counting the number of
    // times each character repeats
    // count the number of times each
    // character repeats from start to end
    var count = new Array(26);
 
    // Store the frequency from s[start...end]
    for(var i = start; i < end; i++)
    {
        count[s.charAt(i) - 'a'] += 1;
    }
 
    // Iterate from [start, end]
    for(var i = start; i < end; i++)
    {
        if (count[s.charAt(i) - 'a'] < k)
        {
             
            // Recursive call for left subpart
            left = longestSubString(start, i,
                                    s, k);
 
            // Recursive call for right subpart
            right = longestSubString(i + 1, end,
                                    s, k);
 
            // Return maximum of left & right
            return Math.max(left, right);
        }
    }
 
    // If all the characters are repeated
    // at least k times
    return end - start;
}
 
// Driver Code
// Given String str
var str = "aabbba";
var k = 3;
 
// Function Call
document.write(longestSubString(0, str.length, str, k) + "\n");
 
// this code is contributed by shivanisinghss2110
 
</script>

6

Complejidad del tiempo: O(N*log ₂ N)