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.
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: el enfoque más simple para resolver el problema dado se analiza en el Conjunto 1 .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(26)
Enfoque divide y vencerás : El enfoque divide y vencerás para el problema dado se analiza en el Conjunto 2 .
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(26)
Enfoque eficiente: los dos enfoques anteriores se pueden optimizar aún más mediante el uso de la técnica de ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Almacene la cantidad de caracteres únicos en la string str en una variable, digamos unique .
- Inicialice una array freq[] de tamaño 26 con {0} y almacene la frecuencia de cada carácter en esta array.
- Iterar sobre el rango [1, único] usando la variable curr_unique . En cada iteración, curr_unique es el número máximo de caracteres únicos que deben estar presentes en la ventana.
- Reinicialice la array freq[] con {0} para almacenar la frecuencia de cada carácter en esta ventana.
- Inicialice start y end como 0 , para almacenar el punto inicial y final de la ventana respectivamente.
- Use dos variables cnt , para almacenar la cantidad de caracteres únicos y countK , para almacenar la cantidad de caracteres con al menos K caracteres repetidos en la ventana actual.
- Ahora, itera un bucle while end < N y realiza lo siguiente:
- Si el valor de cnt es menor o igual a curr_unique, expanda la ventana desde la derecha agregando un carácter al final de la ventana. E incrementa su frecuencia en 1 en freq[] .
- De lo contrario, reduzca la ventana desde la izquierda eliminando un carácter del inicio y disminuyendo su frecuencia en 1 en freq[] .
- En cada paso, actualice los valores de cnt y countK .
- Si el valor de cnt es el mismo que curr_unique y cada carácter aparece al menos K veces , actualice la longitud máxima general y guárdela en ans .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of
// the longest substring
int longestSubstring(string s, int k)
{
// Store the required answer
int ans = 0;
// Create a frequency map of the
// characters of the string
int freq[26] = { 0 };
// Store the length of the string
int n = s.size();
// Traverse the string, s
for (int i = 0; i < n; i++)
// Increment the frequency of
// the current character by 1
freq[s[i] - 'a']++;
// Stores count of unique characters
int unique = 0;
// Find the number of unique
// characters in string
for (int i = 0; i < 26; i++)
if (freq[i] != 0)
unique++;
// Iterate in range [1, unique]
for (int curr_unique = 1;
curr_unique <= unique;
curr_unique++) {
// Initialize frequency of all
// characters as 0
memset(freq, 0, sizeof(freq));
// Stores the start and the
// end of the window
int start = 0, end = 0;
// Stores the current number of
// unique characters and characters
// occurring atleast K times
int cnt = 0, count_k = 0;
while (end < n) {
if (cnt <= curr_unique) {
int ind = s[end] - 'a';
// New unique character
if (freq[ind] == 0)
cnt++;
freq[ind]++;
// New character which
// occurs atleast k times
if (freq[ind] == k)
count_k++;
// Expand window by
// incrementing end by 1
end++;
}
else {
int ind = s[start] - 'a';
// Check if this character
// is present atleast k times
if (freq[ind] == k)
count_k--;
freq[ind]--;
// Check if this character
// is unique
if (freq[ind] == 0)
cnt--;
// Shrink the window by
// incrementing start by 1
start++;
}
// If there are curr_unique
// characters and each character
// is atleast k times
if (cnt == curr_unique
&& count_k == curr_unique)
// Update the overall
// maximum length
ans = max(ans, end - start);
}
}
// return the answer
return ans;
}
// Driver Code
int main()
{
string S = "aabbba";
int K = 3;
cout << longestSubstring(S, K) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the length of
// the longest subString
static void longestSubString(char[] s, int k)
{
// Store the required answer
int ans = 0;
// Create a frequency map of the
// characters of the String
int freq[] = new int[26];
// Store the length of the String
int n = s.length;
// Traverse the String, s
for (int i = 0; i < n; i++)
// Increment the frequency of
// the current character by 1
freq[s[i] - 'a']++;
// Stores count of unique characters
int unique = 0;
// Find the number of unique
// characters in String
for (int i = 0; i < 26; i++)
if (freq[i] != 0)
unique++;
// Iterate in range [1, unique]
for (int curr_unique = 1;
curr_unique <= unique;
curr_unique++)
{
// Initialize frequency of all
// characters as 0
Arrays.fill(freq, 0);
// Stores the start and the
// end of the window
int start = 0, end = 0;
// Stores the current number of
// unique characters and characters
// occurring atleast K times
int cnt = 0, count_k = 0;
while (end < n)
{
if (cnt <= curr_unique)
{
int ind = s[end] - 'a';
// New unique character
if (freq[ind] == 0)
cnt++;
freq[ind]++;
// New character which
// occurs atleast k times
if (freq[ind] == k)
count_k++;
// Expand window by
// incrementing end by 1
end++;
}
else
{
int ind = s[start] - 'a';
// Check if this character
// is present atleast k times
if (freq[ind] == k)
count_k--;
freq[ind]--;
// Check if this character
// is unique
if (freq[ind] == 0)
cnt--;
// Shrink the window by
// incrementing start by 1
start++;
}
// If there are curr_unique
// characters and each character
// is atleast k times
if (cnt == curr_unique
&& count_k == curr_unique)
// Update the overall
// maximum length
ans = Math.max(ans, end - start);
}
}
// Print the answer
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
String S = "aabbba";
int K = 3;
longestSubString(S.toCharArray(), K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to find the length of
# the longest substring
def longestSubstring(s, k) :
# Store the required answer
ans = 0
# Create a frequency map of the
# characters of the string
freq = [0]*26
# Store the length of the string
n = len(s)
# Traverse the string, s
for i in range(n) :
# Increment the frequency of
# the current character by 1
freq[ord(s[i]) - ord('a')] += 1
# Stores count of unique characters
unique = 0
# Find the number of unique
# characters in string
for i in range(26) :
if (freq[i] != 0) :
unique += 1
# Iterate in range [1, unique]
for curr_unique in range(1, unique + 1) :
# Initialize frequency of all
# characters as 0
Freq = [0]*26
# Stores the start and the
# end of the window
start, end = 0, 0
# Stores the current number of
# unique characters and characters
# occurring atleast K times
cnt, count_k = 0, 0
while (end < n) :
if (cnt <= curr_unique) :
ind = ord(s[end]) - ord('a')
# New unique character
if (Freq[ind] == 0) :
cnt += 1
Freq[ind] += 1
# New character which
# occurs atleast k times
if (Freq[ind] == k) :
count_k += 1
# Expand window by
# incrementing end by 1
end += 1
else :
ind = ord(s[start]) - ord('a')
# Check if this character
# is present atleast k times
if (Freq[ind] == k) :
count_k -= 1
Freq[ind] -= 1
# Check if this character
# is unique
if (Freq[ind] == 0) :
cnt -= 1
# Shrink the window by
# incrementing start by 1
start += 1
# If there are curr_unique
# characters and each character
# is atleast k times
if ((cnt == curr_unique) and (count_k == curr_unique)) :
# Update the overall
# maximum length
ans = max(ans, end - start)
# Print the answer
print(ans)
S = "aabbba"
K = 3
longestSubstring(S, K)
# This code is contributed by divyesh072019.
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the length of
// the longest substring
static void longestSubstring(string s, int k)
{
// Store the required answer
int ans = 0;
// Create a frequency map of the
// characters of the string
int[] freq = new int[26];
// Store the length of the string
int n = s.Length;
// Traverse the string, s
for (int i = 0; i < n; i++)
// Increment the frequency of
// the current character by 1
freq[s[i] - 'a']++;
// Stores count of unique characters
int unique = 0;
// Find the number of unique
// characters in string
for (int i = 0; i < 26; i++)
if (freq[i] != 0)
unique++;
// Iterate in range [1, unique]
for (int curr_unique = 1;
curr_unique <= unique;
curr_unique++)
{
// Initialize frequency of all
// characters as 0
for (int i = 0; i < freq.Length; i++)
{
freq[i] = 0;
}
// Stores the start and the
// end of the window
int start = 0, end = 0;
// Stores the current number of
// unique characters and characters
// occurring atleast K times
int cnt = 0, count_k = 0;
while (end < n)
{
if (cnt <= curr_unique)
{
int ind = s[end] - 'a';
// New unique character
if (freq[ind] == 0)
cnt++;
freq[ind]++;
// New character which
// occurs atleast k times
if (freq[ind] == k)
count_k++;
// Expand window by
// incrementing end by 1
end++;
}
else
{
int ind = s[start] - 'a';
// Check if this character
// is present atleast k times
if (freq[ind] == k)
count_k--;
freq[ind]--;
// Check if this character
// is unique
if (freq[ind] == 0)
cnt--;
// Shrink the window by
// incrementing start by 1
start++;
}
// If there are curr_unique
// characters and each character
// is atleast k times
if (cnt == curr_unique
&& count_k == curr_unique)
// Update the overall
// maximum length
ans = Math.Max(ans, end - start);
}
}
// Print the answer
Console.Write(ans);
}
// Driver Code
public static void Main()
{
string S = "aabbba";
int K = 3;
longestSubstring(S, K);
}
}
// This code is contributed by splevel62.
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the length of
// the longest substring
function longestSubstring(s, k)
{
// Store the required answer
let ans = 0;
// Create a frequency map of the
// characters of the string
let freq = new Array(26);
freq.fill(0);
// Store the length of the string
let n = s.length;
// Traverse the string, s
for (let i = 0; i < n; i++)
// Increment the frequency of
// the current character by 1
freq[s[i].charCodeAt() -
'a'.charCodeAt()]++;
// Stores count of unique characters
let unique = 0;
// Find the number of unique
// characters in string
for (let i = 0; i < 26; i++)
if (freq[i] != 0)
unique++;
// Iterate in range [1, unique]
for (let curr_unique = 1;
curr_unique <= unique;
curr_unique++)
{
// Initialize frequency of all
// characters as 0
for (let i = 0; i < freq.length; i++)
{
freq[i] = 0;
}
// Stores the start and the
// end of the window
let start = 0, end = 0;
// Stores the current number of
// unique characters and characters
// occurring atleast K times
let cnt = 0, count_k = 0;
while (end < n)
{
if (cnt <= curr_unique)
{
let ind = s[end].charCodeAt() -
'a'.charCodeAt();
// New unique character
if (freq[ind] == 0)
cnt++;
freq[ind]++;
// New character which
// occurs atleast k times
if (freq[ind] == k)
count_k++;
// Expand window by
// incrementing end by 1
end++;
}
else
{
let ind = s[start].charCodeAt() -
'a'.charCodeAt();
// Check if this character
// is present atleast k times
if (freq[ind] == k)
count_k--;
freq[ind]--;
// Check if this character
// is unique
if (freq[ind] == 0)
cnt--;
// Shrink the window by
// incrementing start by 1
start++;
}
// If there are curr_unique
// characters and each character
// is atleast k times
if (cnt == curr_unique
&& count_k == curr_unique)
// Update the overall
// maximum length
ans = Math.max(ans, end - start);
}
}
// Print the answer
document.write(ans);
}
let S = "aabbba";
let K = 3;
longestSubstring(S, K);
</script>
Producción
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por single__loop y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA