Étant donné une chaîne s composée uniquement de lettres anglaises minuscules et d'un entier k, comptez le nombre total de sous-chaînes (pas nécessairement distinctes) de s qui contiennent exactement k caractères distincts.
Note:
- Une sous-chaîne est une séquence contiguë de caractères dans une chaîne.
- Les sous-chaînes identiques mais apparaissant à des positions différentes doivent chacune être comptées séparément.
Exemples :
Saisir: s = 'abc' k = 2
Sortir: 2
Explication: Les sous-chaînes possibles sont ['ab' 'bc']Saisir: s = 'aba' k = 2
Sortir: 3
Explication: Les sous-chaînes possibles sont ['ab' 'ba' 'aba']Saisir: s = 'AA' k = 1
Sortir: 3
Explication: Les sous-chaînes possibles sont ['a' 'a' 'aa']
Table des matières
- [Approche naïve] Vérification de toutes les sous-chaînes - Temps O(n^2) et espace O(1)
- [Approche efficace] Utilisation de la méthode de la fenêtre glissante - Temps O(n) et espace O(1)
[Approche naïve] Vérification de toutes les sous-chaînes - Temps O(n^2) et espace O(1)
C++L'idée est de vérifier chaque sous-chaîne possible en parcourant toutes les positions de départ (i) et de fin (j) possibles dans la chaîne. Pour chaque sous-chaîne, conservez un tableau booléen pour suivre les caractères distincts et un compteur pour le nombre de caractères distincts. Au fur et à mesure qu'il développe la sous-chaîne de gauche à droite, il met à jour le nombre de caractères distincts en vérifiant si chaque nouveau caractère a déjà été vu. Chaque fois que le nombre de caractères distincts correspond exactement au k donné, le nombre de réponses est incrémenté.
#include
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)); } }
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)); } }
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));
Sortir
2
[Approche efficace] Utilisation de la méthode de la fenêtre glissante - Temps O(n) et espace O(1)
L'idée est d'utiliser fenêtre coulissante technique pour compter efficacement les sous-chaînes avec au plus k caractères distincts, puis soustraire le nombre de sous-chaînes avec au plus k-1 caractères distincts pour obtenir le nombre de sous-chaînes avec exactement k caractères distincts.
Mise en œuvre étape par étape :
- Utilisez une fenêtre coulissante avec un tableau de taille 26 pour suivre les fréquences des caractères.
- Développez la fenêtre à droite en ajoutant des caractères.
- Réduisez la fenêtre à partir de la gauche lorsque les caractères distincts dépassent k.
- Comptez toutes les sous-chaînes valides dans la fenêtre.
- Soustrayez les sous-chaînes avec k-1 caractères distincts de k caractères distincts.
#include
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)); } }
# 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))
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)); } }
// 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));
Sortir
2