logo

TechCodeview

Numărați substraturi cu K caractere distincte

Având în vedere un șir s constând doar din litere engleze mici și un număr întreg K numără numărul total de substraturi (nu neapărat distincte) de S care conțin exact K caractere distincte.
Nota:

  • O substring este o secvență contiguă de caractere într -un șir.
  • Substraturile care sunt identice, dar apar în diferite poziții ar trebui să fie numărate separat.

Exemple:  



Intrare: s = 'abc' k = 2
Ieșire: 2
Explicaţie: Posibilele substraturi sunt ['AB' 'BC']

Intrare: s = 'aba' k = 2
Ieșire: 3
Explicaţie: Posibilele substraturi sunt ['ab' 'ba' 'aba']

Intrare: s = 'aa' k = 1
Ieșire: 3
Explicaţie: Posibilele substraturi sunt ['a' 'a' 'aa']



Tabel de conținut

[Abordare naivă] Verificarea tuturor substraturilor - O (N^2) Timp și O (1) Spațiu

Ideea este de a verifica fiecare substring posibilă iterarea prin toate pozițiile de pornire posibile (I) și pozițiile de încheiere (J) în șir. Pentru fiecare substrat, mențineți un tablou boolean pentru a urmări caractere distincte și un contor pentru numărul de caractere distincte. Pe măsură ce extinde substratul de la stânga la dreapta, actualizează numărul de caractere distinct, verificând dacă fiecare personaj nou a fost văzut înainte. Ori de câte ori numărul de caractere distincte se potrivește exact cu k dat, crește numărul de răspunsuri.

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));

Ieșire 
2

[Abordare eficientă] folosind metoda ferestrei glisante - O (N) Timp și O (1) Spațiu

Ideea este să folosești fereastră glisantă Tehnica de a număra în mod eficient substraturile cu cele mai multe caractere distincte K și apoi scăderea numărului de substraturi cu cele mai multe caractere distincte K-1 pentru a obține numărul de substraturi cu caractere distincte exact k.



Implementare pas cu pas:

  • Utilizați o fereastră glisantă cu o serie de dimensiuni 26 pentru a urmări frecvențele de caractere.
  • Extindeți fereastra la dreapta adăugând caractere.
  • Acordați fereastra de la stânga când caracterele distincte depășesc k.
  • Numărați toate substraturile valide din fereastră.
  • Reduceți substraturile cu caractere distincte K-1 de K personaje distincte.
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));

Ieșire 
2