Dada una string S y un número K . La tarea es encontrar la substring de longitud mínima que tenga exactamente K caracteres distintos.
Nota : la string S consta solo de alfabetos ingleses en minúsculas.
Ejemplos:
Input: S = "ababcb", K = 3 Output: abc Input: S="efecfefd", K = 4 Output: cfefd
Solución simple: la solución simple es considerar cada substring y verificar si contiene k caracteres distintos. En caso afirmativo, compare la longitud de esta substring con la substring de longitud mínima encontrada anteriormente. La complejidad temporal de este enfoque es O(N 2 ), donde N es la longitud de la string S.
Solución eficiente: una solución eficiente es utilizar la técnica de ventana deslizante y hashing. La idea es usar dos punteros st y endpara indicar el punto inicial y final de la ventana deslizante. Inicialmente apunte ambos al principio de la string. Mueva el extremo hacia adelante e incremente el conteo del carácter correspondiente. Si el recuento es uno, se encuentra un nuevo carácter distinto y se incrementa el recuento del número de caracteres distintos. Si el recuento del número de caracteres distintos es mayor que k , avance st y disminuya el recuento de caracteres. Si el recuento de caracteres es cero, se elimina un carácter distinto y el recuento de elementos distintos se puede reducir a k de esta manera. Si el recuento de elementos distintos es k, luego elimine los caracteres del comienzo de la ventana deslizante que tengan un recuento mayor que 1 moviendo st hacia adelante. Compare la longitud de la ventana deslizante actual con la longitud mínima encontrada hasta ahora y actualice si es necesario.
Tenga en cuenta que cada carácter se agrega y elimina de la ventana deslizante como máximo una vez, por lo que cada carácter se recorre dos veces. Por lo tanto, la complejidad del tiempo es lineal.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find minimum length substring
// having exactly k distinct character.
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum length substring
// having exactly k distinct character.
string findMinLenStr(string str, int k)
{
int n = str.length();
// Starting index of sliding window.
int st = 0;
// Ending index of sliding window.
int end = 0;
// To store count of character.
int cnt[26];
memset(cnt, 0, sizeof(cnt));
// To store count of distinct
// character in current sliding
// window.
int distEle = 0;
// To store length of current
// sliding window.
int currlen;
// To store minimum length.
int minlen = n;
// To store starting index of minimum
// length substring.
int startInd = -1;
while (end < n) {
// Increment count of current character
// If this count is one then a new
// distinct character is found in
// sliding window.
cnt[str[end] - 'a']++;
if (cnt[str[end] - 'a'] == 1)
distEle++;
// If number of distinct characters is
// is greater than k, then move starting
// point of sliding window forward,
// until count is k.
if (distEle > k) {
while (st < end && distEle > k) {
if (cnt[str[st] - 'a'] == 1)
distEle--;
cnt[str[st] - 'a']--;
st++;
}
}
// Remove characters from the beginning of
// sliding window having count more than 1
// to minimize length.
if (distEle == k) {
while (st < end && cnt[str[st] - 'a'] > 1) {
cnt[str[st] - 'a']--;
st++;
}
// Compare length with minimum length
// and update if required.
currlen = end - st + 1;
if (currlen < minlen) {
minlen = currlen;
startInd = st;
}
}
end++;
}
// Return minimum length substring.
return str.substr(startInd, minlen);
}
// Driver code
int main()
{
string str = "efecfefd";
int k = 4;
cout << findMinLenStr(str, k);
return 0;
}
Java
// Java program to find minimum length subString
// having exactly k distinct character.
class GFG
{
// Function to find minimum length subString
// having exactly k distinct character.
static String findMinLenStr(String str, int k)
{
int n = str.length();
// Starting index of sliding window.
int st = 0;
// Ending index of sliding window.
int end = 0;
// To store count of character.
int cnt[] = new int[26];
for(int i = 0; i < 26; i++)cnt[i] = 0;
// To store count of distinct
// character in current sliding
// window.
int distEle = 0;
// To store length of current
// sliding window.
int currlen;
// To store minimum length.
int minlen = n;
// To store starting index of minimum
// length subString.
int startInd = -1;
while (end < n)
{
// Increment count of current character
// If this count is one then a new
// distinct character is found in
// sliding window.
cnt[str.charAt(end) - 'a']++;
if (cnt[str.charAt(end) - 'a'] == 1)
distEle++;
// If number of distinct characters is
// is greater than k, then move starting
// point of sliding window forward,
// until count is k.
if (distEle > k)
{
while (st < end && distEle > k)
{
if (cnt[str.charAt(st) - 'a'] == 1)
distEle--;
cnt[str.charAt(st) - 'a']--;
st++;
}
}
// Remove characters from the beginning of
// sliding window having count more than 1
// to minimize length.
if (distEle == k)
{
while (st < end && cnt[str.charAt(st) - 'a'] > 1)
{
cnt[str.charAt(st) - 'a']--;
st++;
}
// Compare length with minimum length
// and update if required.
currlen = end - st + 1;
if (currlen < minlen)
{
minlen = currlen;
startInd = st;
}
}
end++;
}
// Return minimum length subString.
return str.substring(startInd,startInd + minlen);
}
// Driver code
public static void main(String args[])
{
String str = "efecfefd";
int k = 4;
System.out.println(findMinLenStr(str, k));
}
}
// This code is contributed by Arnab Kundu
Python 3
# Python 3 program to find minimum length
# substring having exactly k distinct character.
# Function to find minimum length substring
# having exactly k distinct character.
def findMinLenStr(str, k):
n = len(str)
# Starting index of sliding window.
st = 0
# Ending index of sliding window.
end = 0
# To store count of character.
cnt = [0] * 26
# To store count of distinct
# character in current sliding
# window.
distEle = 0
# To store length of current
# sliding window.
currlen =0
# To store minimum length.
minlen = n
# To store starting index of minimum
# length substring.
startInd = -1
while (end < n):
# Increment count of current character
# If this count is one then a new
# distinct character is found in
# sliding window.
cnt[ord(str[end]) - ord('a')] += 1
if (cnt[ord(str[end]) - ord('a')] == 1):
distEle += 1
# If number of distinct characters is
# is greater than k, then move starting
# point of sliding window forward,
# until count is k.
if (distEle > k):
while (st < end and distEle > k):
if (cnt[ord(str[st]) -
ord('a')] == 1):
distEle -= 1
cnt[ord(str[st]) - ord('a')] -= 1
st += 1
# Remove characters from the beginning of
# sliding window having count more than 1
# to minimize length.
if (distEle == k):
while (st < end and cnt[ord(str[st]) -
ord('a')] > 1):
cnt[ord(str[st]) - ord('a')] -= 1
st += 1
# Compare length with minimum length
# and update if required.
currlen = end - st + 1
if (currlen < minlen):
minlen = currlen
startInd = st
end += 1
# Return minimum length substring.
return str[startInd : startInd + minlen]
# Driver code
if __name__ == "__main__":
str = "efecfefd"
k = 4
print(findMinLenStr(str, k))
# This code is contributed by Ita_c
C#
// C# program to find minimum length subString
// having exactly k distinct character.
using System;
class GFG
{
// Function to find minimum length subString
// having exactly k distinct character.
static String findMinLenStr(string str, int k)
{
int n = str.Length;
// Starting index of sliding window.
int st = 0;
// Ending index of sliding window.
int end = 0;
// To store count of character.
int []cnt = new int[26];
for(int i = 0; i < 26; i++)cnt[i] = 0;
// To store count of distinct
// character in current sliding
// window.
int distEle = 0;
// To store length of current
// sliding window.
int currlen;
// To store minimum length.
int minlen = n;
// To store starting index of minimum
// length subString.
int startInd = -1;
while (end < n)
{
// Increment count of current character
// If this count is one then a new
// distinct character is found in
// sliding window.
cnt[str[end] - 'a']++;
if (cnt[str[end] - 'a'] == 1)
distEle++;
// If number of distinct characters is
// is greater than k, then move starting
// point of sliding window forward,
// until count is k.
if (distEle > k)
{
while (st < end && distEle > k)
{
if (cnt[str[st] - 'a'] == 1)
distEle--;
cnt[str[st] - 'a']--;
st++;
}
}
// Remove characters from the beginning of
// sliding window having count more than 1
// to minimize length.
if (distEle == k)
{
while (st < end && cnt[str[st] - 'a'] > 1)
{
cnt[str[st] - 'a']--;
st++;
}
// Compare length with minimum length
// and update if required.
currlen = end - st + 1;
if (currlen < minlen)
{
minlen = currlen;
startInd = st;
}
}
end++;
}
// Return minimum length subString.
return str.Substring(startInd, minlen);
}
// Driver code
public static void Main()
{
string str = "efecfefd";
int k = 4;
Console.WriteLine(findMinLenStr(str, k));
}
}
// This code is contributed by Ryuga
Javascript
<script>
// Javascript program to find minimum length substring
// having exactly k distinct character.
// Function to find minimum length substring
// having exactly k distinct character.
function findMinLenStr(str, k)
{
var n = str.length;
// Starting index of sliding window.
var st = 0;
// Ending index of sliding window.
var end = 0;
// To store count of character.
var cnt = Array(26).fill(0);
// To store count of distinct
// character in current sliding
// window.
var distEle = 0;
// To store length of current
// sliding window.
var currlen;
// To store minimum length.
var minlen = n;
// To store starting index of minimum
// length substring.
var startInd = -1;
while (end < n) {
// Increment count of current character
// If this count is one then a new
// distinct character is found in
// sliding window.
cnt[str[end].charCodeAt(0) - 'a'.charCodeAt(0)]++;
if (cnt[str[end].charCodeAt(0) - 'a'.charCodeAt(0)] == 1)
distEle++;
// If number of distinct characters is
// is greater than k, then move starting
// point of sliding window forward,
// until count is k.
if (distEle > k) {
while (st < end && distEle > k) {
if (cnt[str[st].charCodeAt(0) - 'a'.charCodeAt(0)] == 1)
distEle--;
cnt[str[st].charCodeAt(0) - 'a'.charCodeAt(0)]--;
st++;
}
}
// Remove characters from the beginning of
// sliding window having count more than 1
// to minimize length.
if (distEle == k) {
while (st < end && cnt[str[st].charCodeAt(0) - 'a'.charCodeAt(0)] > 1) {
cnt[str[st].charCodeAt(0) - 'a'.charCodeAt(0)]--;
st++;
}
// Compare length with minimum length
// and update if required.
currlen = end - st + 1;
if (currlen < minlen) {
minlen = currlen;
startInd = st;
}
}
end++;
}
// Return minimum length substring.
return str.substr(startInd, minlen);
}
// Driver code
var str = "efecfefd";
var k = 4;
document.write( findMinLenStr(str, k));
// This code is contributed by noob2000.
</script>
Producción:
cfefd
Complejidad de tiempo: O(N), donde N es la longitud de la string dada.
Espacio Auxiliar: O(1)