RÄKNA UNDERLAG MED K DISTINKTA TECKEN

Med tanke på en sträng som endast består av små bokstäver och ett heltal räknar det totala antalet underlag (inte nödvändigtvis distinkta) av S som innehåller exakt K distinkta karaktärer.
Notera:

En underlag är en sammanhängande sekvens av tecken i en sträng.
Underlag som är identiska men förekommer vid olika positioner bör räknas separat.

Exempel:

Input: S = 'ABC' K = 2
Produktion: 2
Förklaring: Möjliga underlag är ['AB' 'BC']
Input: S = 'ABA' K = 2
Produktion: 3
Förklaring: Möjliga underlag är ['AB' 'BA' 'ABA']
Word snabbåtkomst verktygsfält
Input: s = 'aa' k = 1
Produktion: 3
Förklaring: Möjliga underlag är ['a' 'a' 'aa']

Innehållsbord

[Naivt tillvägagångssätt] Kontrollera alla underlag - O (n^2) Tid och O (1) utrymme
[Effektiv metod] med hjälp av skjutfönstermetoden - O (n) Tid och O (1) utrymme

[Naivt tillvägagångssätt] Kontrollera alla underlag - O (n^2) Tid och O (1) utrymme

Tanken är att kontrollera alla möjliga underlag genom att iterera genom alla möjliga startpositioner (i) och slutpositioner (j) i strängen. För varje underlag, håll en booleska grupp för att spåra distinkta karaktärer och en räknare för antalet distinkta tecken. När det utvidgar underlaget från vänster till höger uppdaterar det det distinkta karaktärsräkningen genom att kontrollera om varje ny karaktär har sett tidigare. När antalet distinkta tecken exakt matchar den givna k ökar svaret.
kärna java

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 metod] med hjälp av skjutfönstermetoden - O (n) Tid och O (1) utrymme

Tanken är att använda glidfönster Teknik för att effektivt räkna underlag med högst K distinkta karaktärer och sedan subtrahera räkningen av underlag med högst K-1 distinkta tecken för att få antalet underlag med exakt K-distinkta tecken.

Steg för steg implementering:

Använd ett skjutfönster med en rad storlek 26 för att spåra teckenfrekvenser.
Expandera fönstret till höger och lägga till tecken.
Krympa fönstret från vänster när distinkta tecken överstiger k.
Räkna alla giltiga underlag i fönstret.
Subtrahera underlag med K-1 distinkta karaktärer från K distinkta tecken.

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