ПІДРАХУНКИ ПІДРЯДІВ З K РІЗНИХ СИМВОЛАМИ

З огляду на рядок s, що складається лише з малі англійських літер та цілого числа 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 від k різних символів.

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