Dada la string str del alfabeto en minúsculas y un número entero K , la tarea es contar todas las substrings de longitud K que tienen exactamente K caracteres distintos.
Ejemplo:
Entrada: str = “abcc”, K = 2
Salida: 2
Explicación:
Las posibles substrings de longitud K = 2 son
ab : 2 caracteres distintos
bc : 2 caracteres distintos
cc : 1 carácter distinto
Solo existen dos substrings válidas {“ab”, “ antes de Cristo»}.Entrada: str = “aabab”, K = 3
Salida: 0
Explicación:
Las posibles substrings de longitud K = 3 son
aab: 2 caracteres distintos
aba: 2 caracteres distintos
bab: 2 caracteres distintos
No existen substrings de longitud 3 con exactamente 3 caracteres distintos .
Enfoque ingenuo:
la idea es generar todas las substrings de longitud K y, para cada conteo de substrings, una cantidad de caracteres distintos. Si la longitud de una string es N , entonces puede haber N – K + 1 substring de longitud K. La generación de estas substrings requerirá una complejidad O(N) , y la verificación de cada substring requiere una complejidad O(K) , por lo que la complejidad general será como O(N*K).
Enfoque eficiente:
la idea es utilizar la técnica de deslizamiento de ventanas . Mantenga una ventana de tamaño K y lleve un recuento de todos los caracteres en la ventana usando un HashMap . Recorrer la string reduce el recuento del primer carácter de la ventana anterior y agrega la frecuencia del último carácter de la ventana actual en HashMap . Si el recuento de caracteres distintos en una ventana de longitud K es igual a K , incremente la respuesta en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// count of k length substrings
// with k distinct characters
// using sliding window
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// required count of substrings
int countSubstrings(string str, int K)
{
int N = str.size();
// Store the count
int answer = 0;
// Store the count of
// distinct characters
// in every window
unordered_map<char, int> map;
// Store the frequency of
// the first K length substring
for (int i = 0; i < K; i++) {
// Increase frequency of
// i-th character
map[str[i]]++;
}
// If K distinct characters
// exist
if (map.size() == K)
answer++;
// Traverse the rest of the
// substring
for (int i = K; i < N; i++) {
// Increase the frequency
// of the last character
// of the current substring
map[str[i]]++;
// Decrease the frequency
// of the first character
// of the previous substring
map[str[i - K]]--;
// If the character is not present
// in the current substring
if (map[str[i - K]] == 0) {
map.erase(str[i - K]);
}
// If the count of distinct
// characters is 0
if (map.size() == K) {
answer++;
}
}
// Return the count
return answer;
}
// Driver code
int main()
{
// string str
string str = "aabcdabbcdc";
// integer K
int K = 3;
// Print the count of K length
// substrings with k distinct characters
cout << countSubstrings(str, K) << endl;
return 0;
}
Java
// Java program to find the count
// of k length substrings with k
// distinct characters using
// sliding window
import java.util.*;
class GFG{
// Function to return the
// required count of substrings
public static int countSubstrings(String str,
int K)
{
int N = str.length();
// Store the count
int answer = 0;
// Store the count of
// distinct characters
// in every window
Map<Character,
Integer> map = new HashMap<Character,
Integer>();
// Store the frequency of
// the first K length substring
for(int i = 0; i < K; i++)
{
// Increase frequency of
// i-th character
if (map.get(str.charAt(i)) == null)
{
map.put(str.charAt(i), 1);
}
else
{
map.put(str.charAt(i),
map.get(str.charAt(i)) + 1);
}
}
// If K distinct characters
// exist
if (map.size() == K)
answer++;
// Traverse the rest of the
// substring
for(int i = K; i < N; i++)
{
// Increase the frequency
// of the last character
// of the current substring
if (map.get(str.charAt(i)) == null)
{
map.put(str.charAt(i), 1);
}
else
{
map.put(str.charAt(i),
map.get(str.charAt(i)) + 1);
}
// Decrease the frequency
// of the first character
// of the previous substring
map.put(str.charAt(i - K),
map.get(str.charAt(i - K)) - 1);
// If the character is not present
// in the current substring
if (map.get(str.charAt(i - K)) == 0)
{
map.remove(str.charAt(i - K));
}
// If the count of distinct
// characters is 0
if (map.size() == K)
{
answer++;
}
}
// Return the count
return answer;
}
// Driver code
public static void main(String[] args)
{
// string str
String str = "aabcdabbcdc";
// integer K
int K = 3;
// Print the count of K length
// substrings with k distinct characters
System.out.println(countSubstrings(str, K));
}
}
// This code is contributed by grand_master
Python3
# Python3 program to find the
# count of k length substrings
# with k distinct characters
# using sliding window
# Function to return the
# required count of substrings
def countSubstrings(str, K):
N = len(str)
# Store the count
answer = 0
# Store the count of
# distinct characters
# in every window
map = {}
# Store the frequency of
# the first K length substring
for i in range(K):
# Increase frequency of
# i-th character
map[str[i]] = map.get(str[i], 0) + 1
# If K distinct characters
# exist
if (len(map) == K):
answer += 1
# Traverse the rest of the
# substring
for i in range(K, N):
# Increase the frequency
# of the last character
# of the current substring
map[str[i]] = map.get(str[i], 0) + 1
# Decrease the frequency
# of the first character
# of the previous substring
map[str[i - K]] -= 1
# If the character is not present
# in the current substring
if (map[str[i - K]] == 0):
del map[str[i - K]]
# If the count of distinct
# characters is 0
if (len(map) == K):
answer += 1
# Return the count
return answer
# Driver code
if __name__ == '__main__':
str = "aabcdabbcdc"
# Integer K
K = 3
# Print the count of K length
# substrings with k distinct characters
print(countSubstrings(str, K))
# This code is contributed by mohit kumar 29
C#
// C# program to find the count
// of k length substrings with k
// distinct characters using
// sliding window
using System;
using System.Collections.Generic;
class GFG{
// Function to return the
// required count of substrings
public static int countSubstrings(string str,
int K)
{
int N = str.Length;
// Store the count
int answer = 0;
// Store the count of
// distinct characters
// in every window
Dictionary<char,
int> map = new Dictionary<char,
int>();
// Store the frequency of
// the first K length substring
for(int i = 0; i < K; i++)
{
// Increase frequency of
// i-th character
if(!map.ContainsKey(str[i]))
{
map[str[i]] = 1;
}
else
{
map[str[i]]++;
}
}
// If K distinct characters
// exist
if (map.Count == K)
answer++;
// Traverse the rest of the
// substring
for(int i = K; i < N; i++)
{
// Increase the frequency
// of the last character
// of the current substring
if(!map.ContainsKey(str[i]))
{
map[str[i]] = 1;
}
else
{
map[str[i]]++;
}
// Decrease the frequency
// of the first character
// of the previous substring
map[str[i - K]]--;
// If the character is not present
// in the current substring
if (map[str[i - K]] == 0)
{
map.Remove(str[i - K]);
}
// If the count of distinct
// characters is 0
if (map.Count == K)
{
answer++;
}
}
// Return the count
return answer;
}
// Driver code
public static void Main(string[] args)
{
// string str
string str = "aabcdabbcdc";
// integer K
int K = 3;
// Print the count of K length
// substrings with k distinct characters
Console.Write(countSubstrings(str, K));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find the
// count of k length substrings
// with k distinct characters
// using sliding window
// Function to return the
// required count of substrings
function countSubstrings(str, K)
{
var N = str.length;
// Store the count
var answer = 0;
// Store the count of
// distinct characters
// in every window
var map = new Map();
// Store the frequency of
// the first K length substring
for (var i = 0; i < K; i++) {
// Increase frequency of
// i-th character
if(map.has(str[i]))
map.set(str[i], map.get(str[i])+1)
else
map.set(str[i], 1)
}
// If K distinct characters
// exist
if (map.size == K)
answer++;
// Traverse the rest of the
// substring
for (var i = K; i < N; i++) {
// Increase the frequency
// of the last character
// of the current substring
if(map.has(str[i]))
map.set(str[i], map.get(str[i])+1)
else
map.set(str[i], 1)
// Decrease the frequency
// of the first character
// of the previous substring
if(map.has(str[i-K]))
map.set(str[i-K], map.get(str[i-K])-1)
// If the character is not present
// in the current substring
if (map.has(str[i - K]) && map.get(str[i-K])==0) {
map.delete(str[i - K]);
}
// If the count of distinct
// characters is 0
if (map.size == K) {
answer++;
}
}
// Return the count
return answer;
}
// Driver code
// string str
var str = "aabcdabbcdc";
// integer K
var K = 3;
// Print the count of K length
// substrings with k distinct characters
document.write( countSubstrings(str, K) );
</script>
Producción:
5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)