Data una stringa s composta solo da lettere inglesi minuscole e un intero k contare il numero totale di sottostringhe (non necessariamente distinte) di s che contengono esattamente k caratteri distinti.
Nota:
- Una sottostringa è una sequenza contigua di caratteri all'interno di una stringa.
- Le sottostringhe identiche ma presenti in posizioni diverse devono essere conteggiate separatamente.
Esempi:
Ingresso: s = 'abc' k = 2
Produzione: 2
Spiegazione: Le sottostringhe possibili sono ['ab' 'bc']Ingresso: s = 'aba' k = 2
Produzione: 3
Spiegazione: Le sottostringhe possibili sono ['ab' 'ba' 'aba']Ingresso: s = 'AA' k = 1
Produzione: 3
Spiegazione: Le sottostringhe possibili sono ['a' 'a' 'aa']
Sommario
- [Approccio ingenuo] Controllo di tutte le sottostringhe: tempo O(n^2) e spazio O(1).
- [Approccio efficiente] Utilizzo del metodo della finestra scorrevole: tempo O(n) e spazio O(1).
[Approccio ingenuo] Controllo di tutte le sottostringhe: tempo O(n^2) e spazio O(1).
C++L'idea è di controllare ogni possibile sottostringa eseguendo un'iterazione attraverso tutte le possibili posizioni iniziali (i) e finali (j) nella stringa. Per ogni sottostringa mantieni un array booleano per tenere traccia dei caratteri distinti e un contatore per il numero di caratteri distinti. Man mano che espande la sottostringa da sinistra a destra, aggiorna il conteggio dei caratteri distinti controllando se ogni nuovo carattere è stato visto prima. Ogni volta che il numero di caratteri distinti corrisponde esattamente al k specificato, aumenta il conteggio delle risposte.
#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));
Produzione
2
[Approccio efficiente] Utilizzo del metodo della finestra scorrevole: tempo O(n) e spazio O(1).
L'idea è usare finestra scorrevole tecnica per contare in modo efficiente sottostringhe con al massimo k caratteri distinti e quindi sottrarre il conteggio delle sottostringhe con al massimo k-1 caratteri distinti per ottenere il numero di sottostringhe con esattamente k caratteri distinti.
Implementazione passo dopo passo:
- Utilizzare una finestra scorrevole con un array di dimensione 26 per tenere traccia delle frequenze dei caratteri.
- Espandi la finestra a destra aggiungendo caratteri.
- Riduci la finestra da sinistra quando i caratteri distinti superano k.
- Conta tutte le sottostringhe valide all'interno della finestra.
- Sottrai sottostringhe con k-1 caratteri distinti da k caratteri distinti.
#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));
Produzione
2