TÆL SUBSTRENGE MED K FORSKELLIGE TEGN

Givet en streng, der består af kun små bogstaver og et heltal K, tæller det samlede antal understrenge (ikke nødvendigvis forskellige) af S, der indeholder nøjagtigt k forskellige tegn.
Note:

En substring er en sammenhængende sekvens af tegn i en streng.
Substrings, der er identiske, men forekommer i forskellige positioner, bør hver især tælles separat.

Eksempler:

Input: s = 'abc' k = 2
Produktion: 2
Forklaring: Mulige substrings er ['ab' 'bc']
Input: s = 'aba' k = 2
Produktion: 3
Forklaring: Mulige substrenge er ['ab' 'ba' 'aba']
Input: s = 'aa' k = 1
Produktion: 3
Forklaring: Mulige substrings er ['a' 'a' 'aa']

Indholdstabel

[Naiv tilgang] Kontrol af alle substrenge - O (n^2) Tid og O (1) Rum
[Effektiv tilgang] Brug af skydevinduetemetode - O (n) Tid og O (1) Rum

[Naiv tilgang] Kontrol af alle substrenge - O (n^2) Tid og O (1) Rum

Ideen er at kontrollere enhver mulig substring ved at iterere gennem alle mulige startpositioner (I) og slutpositioner (J) i strengen. For hver substring skal du opretholde en boolsk matrix for at spore forskellige tegn og en tæller for antallet af forskellige tegn. Når det udvider substringen fra venstre til højre, opdaterer den det tydelige tegntælling ved at kontrollere, om hver nye karakter er blevet set før. Hver gang antallet af forskellige tegn svarer nøjagtigt til det givne k, øger det svartællingen.

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

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

Produktion

[Effektiv tilgang] Brug af skydevinduetemetode - O (n) Tid og O (1) Rum

Ideen er at bruge glidende vindue Teknik til effektivt at tælle substrings med højst k forskellige tegn og trækker derefter tællingen af substrings med højst K-1 forskellige tegn for at opnå antallet af underlag med nøjagtigt k forskellige tegn.

Trin for trin implementering:

Brug et glidevindue med en række størrelse 26 til at spore karakterfrekvenser.
Udvid vinduet til højre tilføjelse af tegn.
Krymp vinduet fra venstre, når forskellige tegn overstiger k.
Tæl alle gyldige underlag i vinduet.
Træk substrings med K-1 forskellige tegn fra K forskellige tegn.

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