logo

TechCodeview

Contar subcadenas con k caracteres distintos

Dada una cadena s que consta únicamente de letras inglesas minúsculas y un número entero k, cuente el número total de subcadenas (no necesariamente distintas) de s que contienen exactamente k caracteres distintos.
Nota:

conversión y conversión de tipos java
  • Una subcadena es una secuencia contigua de caracteres dentro de una cadena.
  • Las subcadenas que son idénticas pero que aparecen en diferentes posiciones deben contarse por separado.

Ejemplos:  



Aporte: s = 'abc' k = 2
Producción: 2
Explicación: Las posibles subcadenas son ['ab' 'bc']

Aporte: s = 'aba' k = 2
Producción: 3
Explicación: Las posibles subcadenas son ['ab' 'ba' 'aba']

Aporte: s = 'AA' k = 1
Producción: 3
Explicación: Las posibles subcadenas son ['a' 'a' 'aa']



factorial en c

Tabla de contenido

[Enfoque ingenuo] Comprobación de todas las subcadenas: tiempo O(n^2) y espacio O(1)

La idea es verificar cada subcadena posible iterando a través de todas las posiciones iniciales (i) y finales (j) posibles en la cadena. Para cada subcadena, mantenga una matriz booleana para rastrear caracteres distintos y un contador para el número de caracteres distintos. A medida que expande la subcadena de izquierda a derecha, actualiza el recuento de caracteres distintos comprobando si cada carácter nuevo se ha visto antes. Siempre que el número de caracteres distintos coincida exactamente con la k dada, se incrementa el recuento de respuestas.

C++ 
#include    #include  using namespace std; int countSubstr(string &s int k) {  int n = s.length();  int ans = 0;    for (int i=0; i<n; i++) {    // array to check if a character   // is present in substring i..j  vector<bool> map(26 0);  int distinctCnt = 0;    for (int j=i; j<n; j++) {    // if new character is present  // increment distinct count.  if (map[s[j] - 'a'] == false) {  map[s[j] - 'a'] = true;  distinctCnt++;  }    // if distinct count is equal to k.  if (distinctCnt == k) ans++;  }  }    return ans; } int main() {  string s = 'abc';  int k = 2;    cout << countSubstr(s k);  return 0; }
Java 
class GfG {  static int countSubstr(String s int k) {  int n = s.length();  int ans = 0;  for (int i = 0; i < n; i++) {  // array to check if a character   // is present in substring i..j  boolean[] map = new boolean[26];  int distinctCnt = 0;  for (int j = i; j < n; j++) {  // if new character is present  // increment distinct count.  if (!map[s.charAt(j) - 'a']) {  map[s.charAt(j) - 'a'] = true;  distinctCnt++;  }  // if distinct count is equal to k.  if (distinctCnt == k) ans++;  }  }  return ans;  }  public static void main(String[] args) {  String s = 'abc';  int k = 2;  System.out.println(countSubstr(s k));  } }
Python 
def countSubstr(s k): n = len(s) ans = 0 for i in range(n): # array to check if a character  # is present in substring i..j map = [False] * 26 distinctCnt = 0 for j in range(i n): # if new character is present # increment distinct count. if not map[ord(s[j]) - ord('a')]: map[ord(s[j]) - ord('a')] = True distinctCnt += 1 # if distinct count is equal to k. if distinctCnt == k: ans += 1 return ans if __name__ == '__main__': s = 'abc' k = 2 print(countSubstr(s k))
C# 
using System; class GfG {  static int countSubstr(string s int k) {  int n = s.Length;  int ans = 0;  for (int i = 0; i < n; i++) {  // array to check if a character   // is present in substring i..j  bool[] map = new bool[26];  int distinctCnt = 0;  for (int j = i; j < n; j++) {  // if new character is present  // increment distinct count.  if (!map[s[j] - 'a']) {  map[s[j] - 'a'] = true;  distinctCnt++;  }  // if distinct count is equal to k.  if (distinctCnt == k) ans++;  }  }  return ans;  }  static void Main() {  string s = 'abc';  int k = 2;  Console.WriteLine(countSubstr(s k));  } }
JavaScript 
function countSubstr(s k) {  let n = s.length;  let ans = 0;  for (let i = 0; i < n; i++) {  // array to check if a character   // is present in substring i..j  let map = new Array(26).fill(false);  let distinctCnt = 0;  for (let j = i; j < n; j++) {  // if new character is present  // increment distinct count.  if (!map[s.charCodeAt(j) - 'a'.charCodeAt(0)]) {  map[s.charCodeAt(j) - 'a'.charCodeAt(0)] = true;  distinctCnt++;  }  // if distinct count is equal to k.  if (distinctCnt === k) ans++;  }  }  return ans; } // Driver Code let s = 'abc'; let k = 2; console.log(countSubstr(s k));

Producción 
2

[Enfoque eficiente] Uso del método de ventana deslizante: tiempo O(n) y espacio O(1)

La idea es utilizar ventana corredera técnica para contar de manera eficiente subcadenas con como máximo k caracteres distintos y luego restar el recuento de subcadenas con como máximo k-1 caracteres distintos para obtener el número de subcadenas con exactamente k caracteres distintos.



cambiar caso java

Implementación paso a paso:

  • Utilice una ventana deslizante con una matriz de tamaño 26 para realizar un seguimiento de las frecuencias de los caracteres.
  • Expande la ventana hacia la derecha agregando caracteres.
  • Reduce la ventana desde la izquierda cuando los distintos caracteres exceden k.
  • Cuente todas las subcadenas válidas dentro de la ventana.
  • Reste subcadenas con k-1 caracteres distintos de k caracteres distintos.
C++ 
#include    #include  using namespace std; // function which finds the number of  // substrings with atmost k Distinct // characters. int count(string &s int k) {  int n = s.length();  int ans = 0;    // use sliding window technique  vector<int> freq(26 0);  int distinctCnt = 0;  int i = 0;    for (int j = 0; j < n; j++) {    // expand window and add character  freq[s[j] - 'a']++;  if (freq[s[j] - 'a'] == 1) distinctCnt++;    // shrink window if distinct characters exceed k  while (distinctCnt > k) {  freq[s[i] - 'a']--;  if (freq[s[i] - 'a'] == 0) distinctCnt--;  i++;  }    // add number of valid substrings ending at j  ans += j - i + 1;  }    return ans; } // function to find the number of substrings // with exactly k Distinct characters. int countSubstr(string &s int k) {  int n = s.length();  int ans = 0;    // subtract substrings with at most   // k-1 distinct characters from substrings  // with at most k distinct characters  ans = count(s k) - count(s k-1);    return ans; } int main() {  string s = 'abc';  int k = 2;  cout << countSubstr(s k);  return 0; }
Java 
class GfG {  // function which finds the number of   // substrings with atmost k Distinct  // characters.  static int count(String s int k) {  int n = s.length();  int ans = 0;  // use sliding window technique  int[] freq = new int[26];  int distinctCnt = 0;  int i = 0;  for (int j = 0; j < n; j++) {  // expand window and add character  freq[s.charAt(j) - 'a']++;  if (freq[s.charAt(j) - 'a'] == 1) distinctCnt++;  // shrink window if distinct characters exceed k  while (distinctCnt > k) {  freq[s.charAt(i) - 'a']--;  if (freq[s.charAt(i) - 'a'] == 0) distinctCnt--;  i++;  }  // add number of valid substrings ending at j  ans += j - i + 1;  }  return ans;  }  // function to find the number of substrings  // with exactly k Distinct characters.  static int countSubstr(String s int k) {  int n = s.length();  int ans = 0;  // Subtract substrings with at most   // k-1 distinct characters from substrings  // with at most k distinct characters  ans = count(s k) - count(s k - 1);  return ans;  }  public static void main(String[] args) {  String s = 'abc';  int k = 2;  System.out.println(countSubstr(s k));  } }
Python 
# function which finds the number of  # substrings with atmost k Distinct # characters. def count(s k): n = len(s) ans = 0 # ese sliding window technique freq = [0] * 26 distinctCnt = 0 i = 0 for j in range(n): # expand window and add character freq[ord(s[j]) - ord('a')] += 1 if freq[ord(s[j]) - ord('a')] == 1: distinctCnt += 1 # shrink window if distinct characters exceed k while distinctCnt > k: freq[ord(s[i]) - ord('a')] -= 1 if freq[ord(s[i]) - ord('a')] == 0: distinctCnt -= 1 i += 1 # add number of valid substrings ending at j ans += j - i + 1 return ans # function to find the number of substrings # with exactly k Distinct characters. def countSubstr(s k): n = len(s) ans = 0 # subtract substrings with at most  # k-1 distinct characters from substrings # with at most k distinct characters ans = count(s k) - count(s k - 1) return ans if __name__ == '__main__': s = 'abc' k = 2 print(countSubstr(s k))
C# 
using System; class GfG {  // function which finds the number of   // substrings with atmost k Distinct  // characters.  static int count(string s int k) {  int n = s.Length;  int ans = 0;  // use sliding window technique  int[] freq = new int[26];  int distinctCnt = 0;  int i = 0;  for (int j = 0; j < n; j++) {  // expand window and add character  freq[s[j] - 'a']++;  if (freq[s[j] - 'a'] == 1) distinctCnt++;  // shrink window if distinct characters exceed k  while (distinctCnt > k) {  freq[s[i] - 'a']--;  if (freq[s[i] - 'a'] == 0) distinctCnt--;  i++;  }  // add number of valid substrings ending at j  ans += j - i + 1;  }  return ans;  }  // function to find the number of substrings  // with exactly k Distinct characters.  static int countSubstr(string s int k) {  int n = s.Length;  int ans = 0;  // subtract substrings with at most   // k-1 distinct characters from substrings  // with at most k distinct characters  ans = count(s k) - count(s k - 1);  return ans;  }  static void Main() {  string s = 'abc';  int k = 2;  Console.WriteLine(countSubstr(s k));  } }
JavaScript 
// function which finds the number of  // substrings with atmost k Distinct // characters. function count(s k) {  let n = s.length;  let ans = 0;  // use sliding window technique  let freq = new Array(26).fill(0);  let distinctCnt = 0;  let i = 0;  for (let j = 0; j < n; j++) {  // expand window and add character  freq[s.charCodeAt(j) - 'a'.charCodeAt(0)]++;  if (freq[s.charCodeAt(j) - 'a'.charCodeAt(0)] === 1)  distinctCnt++;  // shrink window if distinct characters exceed k  while (distinctCnt > k) {  freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]--;  if (freq[s.charCodeAt(i) - 'a'.charCodeAt(0)] === 0)  distinctCnt--;  i++;  }  // add number of valid substrings ending at j  ans += j - i + 1;  }  return ans; } // sunction to find the number of substrings // with exactly k Distinct characters. function countSubstr(s k) {  let n = s.length;  let ans = 0;  // subtract substrings with at most   // k-1 distinct characters from substrings  // with at most k distinct characters  ans = count(s k) - count(s k - 1);  return ans; } // Driver Code let s = 'abc'; let k = 2; console.log(countSubstr(s k));

Producción 
2