Étant donné une chaîne et un entier k, trouvez le nombre de sous-chaînes dans lesquelles tous les différents caractères apparaissent exactement k fois.
Exemples :
Input : s = 'aabbcc' k = 2 Output : 6 The substrings are aa bb cc aabb bbcc and aabbcc. Input : s = 'aabccc' k = 2 Output : 3 There are three substrings aa cc and cc
Approche naïve : L'idée est de parcourir toutes les sous-chaînes. Nous fixons un point de départ traversant toutes les sous-chaînes en commençant par le point choisi, nous continuons à incrémenter les fréquences de tous les caractères. Si toutes les fréquences deviennent k, nous incrémentons le résultat. Si le nombre d'une fréquence devient supérieur à k, nous cassons et changeons le point de départ.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++// C++ program to count number of substrings // with counts of distinct characters as k. #include
// Java program to count number of substrings // with counts of distinct characters as k. import java.io.*; class GFG { static int MAX_CHAR = 26; // Returns true if all values // in freq[] are either 0 or k. static boolean check(int freq[] int k) { for (int i = 0; i < MAX_CHAR; i++) if (freq[i] !=0 && freq[i] != k) return false; return true; } // Returns count of substrings where frequency // of every present character is k static int substrings(String s int k) { int res = 0; // Initialize result // Pick a starting point for (int i = 0; i< s.length(); i++) { // Initialize all frequencies as 0 // for this starting point int freq[] = new int[MAX_CHAR]; // One by one pick ending points for (int j = i; j<s.length(); j++) { // Increment frequency of current char int index = s.charAt(j) - 'a'; freq[index]++; // If frequency becomes more than // k we can't have more substrings // starting with i if (freq[index] > k) break; // If frequency becomes k then check // other frequencies as well. else if (freq[index] == k && check(freq k) == true) res++; } } return res; } // Driver code public static void main(String[] args) { String s = 'aabbcc'; int k = 2; System.out.println(substrings(s k)); s = 'aabbc'; k = 2; System.out.println(substrings(s k)); } } // This code has been contributed by 29AjayKumar
# Python3 program to count number of substrings # with counts of distinct characters as k. MAX_CHAR = 26 # Returns true if all values # in freq[] are either 0 or k. def check(freq k): for i in range(0 MAX_CHAR): if(freq[i] and freq[i] != k): return False return True # Returns count of substrings where # frequency of every present character is k def substrings(s k): res = 0 # Initialize result # Pick a starting point for i in range(0 len(s)): # Initialize all frequencies as 0 # for this starting point freq = [0] * MAX_CHAR # One by one pick ending points for j in range(i len(s)): # Increment frequency of current char index = ord(s[j]) - ord('a') freq[index] += 1 # If frequency becomes more than # k we can't have more substrings # starting with i if(freq[index] > k): break # If frequency becomes k then check # other frequencies as well elif(freq[index] == k and check(freq k) == True): res += 1 return res # Driver Code if __name__ == '__main__': s = 'aabbcc' k = 2 print(substrings(s k)) s = 'aabbc'; k = 2; print(substrings(s k)) # This code is contributed # by Sairahul Jella
// C# program to count number of substrings // with counts of distinct characters as k. using System; class GFG { static int MAX_CHAR = 26; // Returns true if all values // in freq[] are either 0 or k. static bool check(int []freq int k) { for (int i = 0; i < MAX_CHAR; i++) if (freq[i] != 0 && freq[i] != k) return false; return true; } // Returns count of substrings where frequency // of every present character is k static int substrings(String s int k) { int res = 0; // Initialize result // Pick a starting point for (int i = 0; i < s.Length; i++) { // Initialize all frequencies as 0 // for this starting point int []freq = new int[MAX_CHAR]; // One by one pick ending points for (int j = i; j < s.Length; j++) { // Increment frequency of current char int index = s[j] - 'a'; freq[index]++; // If frequency becomes more than // k we can't have more substrings // starting with i if (freq[index] > k) break; // If frequency becomes k then check // other frequencies as well. else if (freq[index] == k && check(freq k) == true) res++; } } return res; } // Driver code public static void Main(String[] args) { String s = 'aabbcc'; int k = 2; Console.WriteLine(substrings(s k)); s = 'aabbc'; k = 2; Console.WriteLine(substrings(s k)); } } /* This code contributed by PrinciRaj1992 */
// PHP program to count number of substrings // with counts of distinct characters as k. $MAX_CHAR = 26; // Returns true if all values // in freq[] are either 0 or k. function check(&$freq $k) { global $MAX_CHAR; for ($i = 0; $i < $MAX_CHAR; $i++) if ($freq[$i] && $freq[$i] != $k) return false; return true; } // Returns count of substrings where frequency // of every present character is k function substrings($s $k) { global $MAX_CHAR; $res = 0; // Initialize result // Pick a starting point for ($i = 0; $i < strlen($s); $i++) { // Initialize all frequencies as 0 // for this starting point $freq = array_fill(0 $MAX_CHARNULL); // One by one pick ending points for ($j = $i; $j < strlen($s); $j++) { // Increment frequency of current char $index = ord($s[$j]) - ord('a'); $freq[$index]++; // If frequency becomes more than // k we can't have more substrings // starting with i if ($freq[$index] > $k) break; // If frequency becomes k then check // other frequencies as well. else if ($freq[$index] == $k && check($freq $k) == true) $res++; } } return $res; } // Driver code $s = 'aabbcc'; $k = 2; echo substrings($s $k).'n'; $s = 'aabbc'; $k = 2; echo substrings($s $k).'n'; // This code is contributed by Ita_c. ?> <script> // Javascript program to count number of // substrings with counts of distinct // characters as k. let MAX_CHAR = 26; // Returns true if all values // in freq[] are either 0 or k. function check(freqk) { for(let i = 0; i < MAX_CHAR; i++) if (freq[i] != 0 && freq[i] != k) return false; return true; } // Returns count of substrings where frequency // of every present character is k function substrings(s k) { // Initialize result let res = 0; // Pick a starting point for(let i = 0; i< s.length; i++) { // Initialize all frequencies as 0 // for this starting point let freq = new Array(MAX_CHAR); for(let i = 0; i < freq.length ;i++) { freq[i] = 0; } // One by one pick ending points for(let j = i; j < s.length; j++) { // Increment frequency of current char let index = s[j].charCodeAt(0) - 'a'.charCodeAt(0); freq[index]++; // If frequency becomes more than // k we can't have more substrings // starting with i if (freq[index] > k) break; // If frequency becomes k then check // other frequencies as well. else if (freq[index] == k && check(freq k) == true) res++; } } return res; } // Driver code let s = 'aabbcc'; let k = 2; document.write(substrings(s k) + '
'); s = 'aabbc'; k = 2; document.write(substrings(s k) + '
'); // This code is contributed by avanitrachhadiya2155 </script>
Sortir
6 3
Complexité temporelle : O(n*n) où n est la longueur de la chaîne d'entrée. La fonction Check() exécute une boucle de longueur constante de 0 à MAX_CHAR (c'est-à-dire 26 toujours), donc cette fonction check() s'exécute en un temps O(MAX_CHAR), donc la complexité temporelle est O(MAX_CHAR*n*n)=O(n^2).
Espace auxiliaire : O(1)
Approche efficace : Après une observation très attentive, nous pouvons voir qu'il suffit de vérifier la même chose pour les sous-chaînes de longueur Ktimes i forall iisin[1 D] où D est le nombre de caractères distincts présents dans la chaîne donnée.
Argument:
Considérons une sous-chaîne S_{i+1}S_{i+2}dots S_{i+p} de longueur 'p'. Si cette sous-chaîne a « m » caractères distincts et que chaque caractère distinct apparaît exactement « K » fois, alors la longueur de la sous-chaîne « p » est donnée par p = Ktimes m. Puisque 'p ' est toujours un multiple de 'K' et 1le mle 26 pour la chaîne donnée, il suffit de parcourir les sous-chaînes dont la longueur est divisible par 'K' et ayant m 1 le m le 26 caractères distincts. Nous utiliserons la fenêtre coulissante pour parcourir les sous-chaînes de longueur fixe.
Solution:
- Trouvez le nombre de caractères distincts présents dans la chaîne donnée. Que ce soit D.
- Pour chaque i 1le ile D, procédez comme suit
- Parcourez les sous-chaînes de longueur $i fois K$ à l'aide d'une fenêtre glissante.
- Vérifiez s'ils satisfont à la condition - Tous les caractères distincts de la sous-chaîne apparaissent exactement K fois.
- S'ils satisfont à la condition, incrémentez le décompte.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++#include
#include
import java.util.*; class GFG { static boolean have_same_frequency(int[] freq int k) { for (int i = 0; i < 26; i++) { if (freq[i] != 0 && freq[i] != k) { return false; } } return true; } static int count_substrings(String s int k) { int count = 0; int distinct = 0; boolean[] have = new boolean[26]; Arrays.fill(have false); for (int i = 0; i < s.length(); i++) { have[((int)(s.charAt(i) - 'a'))] = true; } for (int i = 0; i < 26; i++) { if (have[i]) { distinct++; } } for (int length = 1; length <= distinct; length++) { int window_length = length * k; int[] freq = new int[26]; Arrays.fill(freq 0); int window_start = 0; int window_end = window_start + window_length - 1; for (int i = window_start; i <= Math.min(window_end s.length() - 1); i++) { freq[((int)(s.charAt(i) - 'a'))]++; } while (window_end < s.length()) { if (have_same_frequency(freq k)) { count++; } freq[( (int)(s.charAt(window_start) - 'a'))]--; window_start++; window_end++; if (window_end < s.length()) { freq[((int)(s.charAt(window_end) - 'a'))]++; } } } return count; } public static void main(String[] args) { String s = 'aabbcc'; int k = 2; System.out.println(count_substrings(s k)); s = 'aabbc'; k = 2; System.out.println(count_substrings(s k)); } }
from collections import defaultdict def have_same_frequency(freq: defaultdict k: int): return all([freq[i] == k or freq[i] == 0 for i in freq]) def count_substrings(s: str k: int) -> int: count = 0 distinct = len(set([i for i in s])) for length in range(1 distinct + 1): window_length = length * k freq = defaultdict(int) window_start = 0 window_end = window_start + window_length - 1 for i in range(window_start min(window_end + 1 len(s))): freq[s[i]] += 1 while window_end < len(s): if have_same_frequency(freq k): count += 1 freq[s[window_start]] -= 1 window_start += 1 window_end += 1 if window_end < len(s): freq[s[window_end]] += 1 return count if __name__ == '__main__': s = 'aabbcc' k = 2 print(count_substrings(s k)) s = 'aabbc' k = 2 print(count_substrings(s k))
using System; class GFG{ static bool have_same_frequency(int[] freq int k) { for(int i = 0; i < 26; i++) { if (freq[i] != 0 && freq[i] != k) { return false; } } return true; } static int count_substrings(string s int k) { int count = 0; int distinct = 0; bool[] have = new bool[26]; Array.Fill(have false); for(int i = 0; i < s.Length; i++) { have[((int)(s[i] - 'a'))] = true; } for(int i = 0; i < 26; i++) { if (have[i]) { distinct++; } } for(int length = 1; length <= distinct; length++) { int window_length = length * k; int[] freq = new int[26]; Array.Fill(freq 0); int window_start = 0; int window_end = window_start + window_length - 1; for(int i = window_start; i <= Math.Min(window_end s.Length - 1); i++) { freq[((int)(s[i] - 'a'))]++; } while (window_end < s.Length) { if (have_same_frequency(freq k)) { count++; } freq[((int)(s[window_start] - 'a'))]--; window_start++; window_end++; if (window_end < s.Length) { freq[((int)(s[window_end] - 'a'))]++; } } } return count; } // Driver code public static void Main(string[] args) { string s = 'aabbcc'; int k = 2; Console.WriteLine(count_substrings(s k)); s = 'aabbc'; k = 2; Console.WriteLine(count_substrings(s k)); } } // This code is contributed by gaurav01
<script> function have_same_frequency(freqk) { for (let i = 0; i < 26; i++) { if (freq[i] != 0 && freq[i] != k) { return false; } } return true; } function count_substrings(sk) { let count = 0; let distinct = 0; let have = new Array(26); for(let i=0;i<26;i++) { have[i]=false; } for (let i = 0; i < s.length; i++) { have[((s[i].charCodeAt(0) - 'a'.charCodeAt(0)))] = true; } for (let i = 0; i < 26; i++) { if (have[i]) { distinct++; } } for (let length = 1; length <= distinct; length++) { let window_length = length * k; let freq = new Array(26); for(let i=0;i<26;i++) freq[i]=0; let window_start = 0; let window_end = window_start + window_length - 1; for (let i = window_start; i <= Math.min(window_end s.length - 1); i++) { freq[((s[i].charCodeAt(0) - 'a'.charCodeAt(0)))]++; } while (window_end < s.length) { if (have_same_frequency(freq k)) { count++; } freq[( (s[window_start].charCodeAt(0) - 'a'.charCodeAt(0)))]--; window_start++; window_end++; if (window_end < s.length) { freq[(s[window_end].charCodeAt(0) - 'a'.charCodeAt(0))]++; } } } return count; } let s = 'aabbcc'; let k = 2; document.write(count_substrings(s k)+'
'); s = 'aabbc'; k = 2; document.write(count_substrings(s k)+'
'); // This code is contributed by rag2127 </script>
Sortir
6 3
Complexité temporelle : O(N * D) où D est le nombre de caractères distincts présents dans la chaîne et N est la longueur de la chaîne.
Espace auxiliaire : SUR)
Créer un quiz