Cuente el número de substrings que tienen al menos K caracteres distintos

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:

  1. “abc”: Recuento de caracteres distintos = 3.
  2. “abcc”: Recuento de caracteres distintos = 3.
  3. “abcca”: Recuento de caracteres distintos = 3.
  4. “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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *