ПРЕБРОЙТЕ ПОДСИЛВАНИЯТА С K РАЗЛИЧНИ ЗНАЦИ

Като се има предвид низ, състоящ се само от малки букви и цяло число k, пребройте общия брой подземни (не непременно различни) на s, които съдържат точно k различни знаци.
Забележка:

Подземването е съседна последователност от знаци в рамките на низ.
Подземните, които са идентични, но се срещат на различни позиции, трябва да се броят отделно.

Примери:

Вход: s = 'abc' k = 2
Резултат: 2
Обяснение: Възможните подсилвания са ['AB' 'BC']
Вход: s = 'aba' k = 2
Резултат: 3
Обяснение: Възможните подсилвания са ['ab' 'ba' 'aba']
Вход: s = 'aa' k = 1
Резултат: 3
Обяснение: Възможните подсилвания са ['a' 'a' 'aa']

Съдържание

[Наивен подход] Проверка на всички подсилвания - O (n^2) време и o (1) пространство
[Ефективен подход] Използване на метод на плъзгащ се прозорец - O (n) време и o (1) пространство

[Наивен подход] Проверка на всички подсилвания - O (n^2) време и o (1) пространство

Идеята е да се провери всички възможни субстринг чрез повторение през всички възможни начални позиции (i) и крайни позиции (j) в низа. За всеки подводник поддържайте булев масив, за да проследявате различни знаци и брояч за броя на различни знаци. Тъй като разширява подреда отляво надясно, той актуализира отчетливия брой на символите, като проверява дали всеки нов герой е бил виждан преди. Всеки път, когато броят на отделните знаци точно съвпада с дадения K, той увеличава броя на отговорите.

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

Изход

[Ефективен подход] Използване на метод на плъзгащ се прозорец - O (n) време и o (1) пространство

Идеята е да се използва Плъзгащ се прозорец Техника за ефективно преброяване на подсилванията с най-много k различни символи и след това изваждане на броя на субстрациите с най-много K-1 различни знаци, за да се получат броя на субстраните с точно k различни знаци.

Стъпка по стъпка изпълнение:

Използвайте плъзгащ се прозорец с масив с размер 26, за да проследявате честотите на характера.
Разширете прозореца надясно Добавяне на символи.
Свийте прозореца отляво, когато отделни знаци надвишават k.
Пребройте всички валидни подсилвания в прозореца.
Извадете субстрани с K-1 различни символи от различни знаци.

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