logo

TechCodeview

Telle underlag med K -distinkte tegn

Gitt en streng som består av bare små bokstaver og et heltall k teller det totale antallet underlag (ikke nødvendigvis distinkte) av s som inneholder nøyaktig k distinkte tegn.
Note:

  • En substring er en sammenhengende sekvens av tegn i en streng.
  • Substrlinger som er identiske, men forekommer i forskjellige posisjoner, bør telles hver for seg.

Eksempler:  



: s = 'abc' k = 2
Produksjon: 2
Forklaring: Mulige underlag er ['AB' 'BC']

: s = 'aba' k = 2
Produksjon: 3
Forklaring: Mulige underlag er ['ab' 'ba' 'aba']

: s = 'aa' k = 1
Produksjon: 3
Forklaring: Mulige underlag er ['A' 'A' 'AA']



Tabell over innhold

[Naiv tilnærming] Kontroller alle underlag - O (N^2) Tid og O (1) plass

Tanken er å sjekke alle mulige substring ved å iterere gjennom alle mulige startposisjoner (I) og sluttposisjoner (J) i strengen. For hver substring opprettholder en boolsk matrise for å spore distinkte tegn og en teller for antall distinkte tegn. Når den utvider substringen fra venstre mot høyre, oppdaterer den det distinkte karaktertellingen ved å sjekke om hvert nye tegn har blitt sett før. Hver gang antallet distinkte karakterer nøyaktig samsvarer med de gitte k, øker det svaretellingen.

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

Produksjon 
2

[Effektiv tilnærming] Bruke glidende vindusmetode - o (n) tid og o (1) plass

Tanken er å bruke skyve vindu Teknikk for å effektivt telle underlag med høyst K-distinkte tegn og deretter trekke tellingen av underlag med høyst K-1 distinkte tegn for å oppnå antall underlag med nøyaktig K distinkte tegn.



Trinn for trinns implementering:

  • Bruk et skyvevindu med en rekke størrelse 26 for å spore karakterfrekvenser.
  • Utvid vinduet til høyre og legge til tegn.
  • Krymp vinduet fra venstre når distinkte tegn overstiger k.
  • Tell alle gyldige underlag i vinduet.
  • Trekk underlag med K-1 distinkte tegn fra K-distinkte 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; }
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));

Produksjon 
2