logo

TechCodeview

Comptar les substrings amb K diferents caràcters

Tenint en compte una cadena S que consisteix en només lletres angleses en minúscules i un nombre enter K, compten el nombre total de substrings (no necessàriament diferents) de S que contenen exactament k diferents caràcters.
NOTA:

  • Una substring és una seqüència contigua de caràcters dins d’una cadena.
  • Les substrings que són idèntiques, però que es produeixen en diferents posicions, s’haurien de comptabilitzar per separat.

Exemples:  



bash altrament si

Entrada: s = 'abc' k = 2
Sortida: 2
Explicació: Les substrings possibles són ['AB' 'BC']

Entrada: s = 'aba' k = 2
Sortida: 3
Explicació: Les substrings possibles són ['ab' 'ba' 'aba']

Entrada: s = 'aa' k = 1
Sortida: 3
Explicació: Les substrings possibles són ['a' 'a' 'aa']



Taula de contingut

sincronització de fils

[Enfocament ingenu] Comprovació de totes les substrings - O (n^2) Temps i O (1) Espai

La idea és comprovar cada substring possible iterant -se a través de totes les posicions inicials possibles (i) i les posicions finals (J) a la cadena. Per a cada substring, manteniu una matriu booleana per fer un seguiment de caràcters diferents i un comptador per al nombre de personatges diferents. A mesura que amplia la substància d’esquerra a dreta, actualitza el recompte de personatges diferents comprovant si s’ha vist cada nou personatge abans. Sempre que el nombre de caràcters diferents coincideix exactament amb la K IT, incrementa el recompte de respostes.

cadena java amb format
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ó 
2

[Aproximació eficient] Mètode de la finestra lliscant - O (n) Temps i O (1) Espai

La idea és utilitzar finestra lliscant Tècnica per comptar de manera eficient les substrings amb els caràcters diferents de K i, a continuació, restar el recompte de substrings amb un màxim de caràcters diferents de K-1 per obtenir el nombre de substrings amb caràcters diferents.



Implementació pas a pas:

  • Utilitzeu una finestra lliscant amb una matriu de mida 26 per fer un seguiment de les freqüències de caràcters.
  • Amplieu la finestra a la dreta afegint caràcters.
  • Reduir la finestra de l'esquerra quan els caràcters diferents superen el k.
  • Compteu totes les substrings vàlides dins de la finestra.
  • Resteu substrings amb personatges diferents de K-1 de K diferents caràcters.
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ó 
2