Dada una string S que consta de N caracteres y un entero positivo K , la tarea es contar el número de substrings que tienen al menos K caracteres distintos.
Ejemplos:
Entrada: S = “abcca”, K = 3
Salida: 4
Explicación:
Las substrings que contienen al menos K(= 3) caracteres distintos son:
- “abc”: Recuento de caracteres distintos = 3.
- “abcc”: Recuento de caracteres distintos = 3.
- “abcca”: Recuento de caracteres distintos = 3.
- “bcca”: Recuento de caracteres distintos = 3.
Por lo tanto, el recuento total de substrings es 4.
Entrada: S = “abcca”, K = 4
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las substrings de la string dada y contar esas substrings que tienen al menos K caracteres distintos en ellas. Después de verificar todas las substrings, imprima el recuento total obtenido como resultado.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(256)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso del concepto de ventana deslizante y hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 para almacenar el recuento de substrings que tengan al menos K caracteres distintos.
- Inicialice dos punteros, begin y end para almacenar el punto inicial y final de la ventana deslizante.
- Inicialice un HashMap , diga M para almacenar la frecuencia de los caracteres en la ventana.
- Iterar hasta que end sea menor que N y realizar los siguientes pasos:
- Incluya el carácter al final de la ventana, incrementando el valor de S[end] en M en 1 .
- Iterar hasta que el tamaño de M sea menor que K y realizar los siguientes pasos:
- Elimine los caracteres del inicio de la ventana disminuyendo el valor de S[comienzo] en M en 1 .
- Si su frecuencia llega a ser 0 , entonces bórrelo del mapa M .
- Cuente todas las substrings desde el inicio hasta N incrementando ans por (N – final + 1) .
- 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 count number of substrings
// having atleast k distinct characters
void atleastkDistinctChars(string s, int k)
{
// Stores the size of the string
int n = s.size();
// Initialize a HashMap
unordered_map<char, int> mp;
// Stores the start and end
// indices of sliding window
int begin = 0, end = 0;
// Stores the required result
int ans = 0;
// Iterate while the end
// pointer is less than n
while (end < n) {
// Include the character at
// the end of the window
char c = s[end];
mp++;
// Increment end pointer by 1
end++;
// Iterate until count of distinct
// characters becomes less than K
while (mp.size() >= k) {
// Remove the character from
// the beginning of window
char pre = s[begin];
mp[pre]--;
// If its frequency is 0,
// remove it from the map
if (mp[pre] == 0) {
mp.erase(pre);
}
// Update the answer
ans += s.length() - end + 1;
begin++;
}
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
string S = "abcca";
int K = 3;
atleastkDistinctChars(S, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to count number of substrings
// having atleast k distinct characters
static void atleastkDistinctChars(String s, int k)
{
// Stores the size of the string
int n = s.length();
// Initialize a HashMap
Map<Character, Integer> mp = new HashMap<>();
// Stores the start and end
// indices of sliding window
int begin = 0, end = 0;
// Stores the required result
int ans = 0;
// Iterate while the end
// pointer is less than n
while (end < n) {
// Include the character at
// the end of the window
char c = s.charAt(end);
mp.put(c,mp.getOrDefault(c,0)+1);
// Increment end pointer by 1
end++;
// Iterate until count of distinct
// characters becomes less than K
while (mp.size() >= k) {
// Remove the character from
// the beginning of window
char pre = s.charAt(begin);
mp.put(pre,mp.getOrDefault(pre,0)-1);
// If its frequency is 0,
// remove it from the map
if (mp.get(pre)==0){
mp.remove(pre);
}
// Update the answer
ans += s.length() - end + 1;
begin++;
}
}
// Print the result
System.out.println(ans);
}
// Driver code
public static void main (String[] args)
{
// Given inputs
String S = "abcca";
int K = 3;
atleastkDistinctChars(S, K);
}
}
// This code is contributed by offbeat
Python3
# Python 3 program for the above approach from collections import defaultdict # Function to count number of substrings # having atleast k distinct characters def atleastkDistinctChars(s, k): # Stores the size of the string n = len(s) # Initialize a HashMap mp = defaultdict(int) # Stores the start and end # indices of sliding window begin = 0 end = 0 # Stores the required result ans = 0 # Iterate while the end # pointer is less than n while (end < n): # Include the character at # the end of the window c = s[end] mp += 1 # Increment end pointer by 1 end += 1 # Iterate until count of distinct # characters becomes less than K while (len(mp) >= k): # Remove the character from # the beginning of window pre = s[begin] mp[pre] -= 1 # If its frequency is 0, # remove it from the map if (mp[pre] == 0): del mp[pre] # Update the answer ans += len(s) - end + 1 begin += 1 # Print the result print(ans) # Driver Code if __name__ == "__main__": S = "abcca" K = 3 atleastkDistinctChars(S, K) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count number of substrings
// having atleast k distinct characters
static void atleastkDistinctChars(string s, int k)
{
// Stores the size of the string
int n = s.Length;
// Initialize a HashMap
Dictionary<char,
int> mp = new Dictionary<char,
int>();
// Stores the start and end
// indices of sliding window
int begin = 0, end = 0;
// Stores the required result
int ans = 0;
// Iterate while the end
// pointer is less than n
while (end < n)
{
// Include the character at
// the end of the window
char c = s[end];
if (mp.ContainsKey(c))
mp++;
else
mp.Add(c, 1);
// Increment end pointer by 1
end++;
// Iterate until count of distinct
// characters becomes less than K
while (mp.Count >= k)
{
// Remove the character from
// the beginning of window
char pre = s[begin];
mp[pre]--;
// If its frequency is 0,
// remove it from the map
if (mp[pre] == 0)
{
mp.Remove(pre);
}
// Update the answer
ans += s.Length - end + 1;
begin++;
}
}
// Print the result
Console.Write(ans);
}
// Driver Code
public static void Main()
{
string S = "abcca";
int K = 3;
atleastkDistinctChars(S, K);
}
}
// This code is contributed by bgangwar59
Javascript
<script>
// Javascript program for the above approach
// Function to count number of substrings
// having atleast k distinct characters
function atleastkDistinctChars(s,k)
{
// Stores the size of the string
let n = s.length;
// Initialize a HashMap
let mp = new Map();
// Stores the start and end
// indices of sliding window
let begin = 0, end = 0;
// Stores the required result
let ans = 0;
// Iterate while the end
// pointer is less than n
while (end < n)
{
// Include the character at
// the end of the window
let c = s[end];
if (mp.has(c))
mp.set(c,mp.get(c)+1);
else
mp.set(c, 1);
// Increment end pointer by 1
end++;
// Iterate until count of distinct
// characters becomes less than K
while (mp.size >= k)
{
// Remove the character from
// the beginning of window
let pre = s[begin];
mp.set(pre,mp.get(pre)-1);
// If its frequency is 0,
// remove it from the map
if (mp.get(pre) == 0)
{
mp.delete(pre);
}
// Update the answer
ans += s.length - end + 1;
begin++;
}
}
// Print the result
document.write(ans);
}
// Driver Code
let S = "abcca";
let K = 3;
atleastkDistinctChars(S, K);
// This code is contributed by rag2127
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(256)
Publicación traducida automáticamente
Artículo escrito por curious_person y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA