Mając dany ciąg znaków i liczbę całkowitą k, znajdź liczbę podciągów, w których wszystkie różne znaki występują dokładnie k razy.
Przykłady:
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
Naiwne podejście: Chodzi o to, aby przejść przez wszystkie podciągi. Ustalamy przejście punktu początkowego przez wszystkie podciągi, zaczynając od wybranego punktu, zwiększając częstotliwości wszystkich znaków. Jeśli wszystkie częstotliwości osiągną wartość k, zwiększamy wynik. Jeśli liczba dowolnej częstotliwości przekracza k, przerywamy i zmieniamy punkt początkowy.
Poniżej implementacja powyższego podejścia:
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>
Wyjście
6 3
Złożoność czasowa: O(n*n) gdzie n jest długością ciągu wejściowego. Funkcja Check() uruchamia pętlę o stałej długości od 0 do MAX_CHAR (tj. 26 zawsze), więc ta funkcja check() działa w czasie O(MAX_CHAR), więc złożoność czasowa wynosi O(MAX_CHAR*n*n)=O(n^2).
Przestrzeń pomocnicza: O(1)
Efektywne podejście: Po bardzo uważnej obserwacji widać, że wystarczy sprawdzić to samo dla podciągów o długości Ktimes i forall iisin[1 D] , gdzie D jest liczbą różnych znaków występujących w danym ciągu.
Argument:
Rozważmy podciąg S_{i+1}S_{i+2}kropek S_{i+p} o długości „p”. Jeśli ten podciąg ma „m” różnych znaków i każdy odrębny znak występuje dokładnie „K” razy, wówczas długość podciągu „p” wyraża się przez p = K razy m. Ponieważ „p ” jest zawsze wielokrotnością „K” i 1le mle 26 dla danego ciągu wystarczy iterować po podciągach, których długość jest podzielna przez „K” i mających m 1 le m le 26 różnych znaków. Będziemy używać okna przesuwnego do iteracji po podciągach o stałej długości.
Rozwiązanie:
- Znajdź liczbę różnych znaków występujących w podanym ciągu. Niech będzie D.
- Dla każdego i 1 pliku D wykonaj następujące czynności
- Iteruj po podciągach o długości $i razy K$, używając przesuwanego okna.
- Sprawdź, czy spełniają warunek - Wszystkie różne znaki w podciągu występują dokładnie K razy.
- Jeśli spełniają warunek, zwiększ liczbę.
Poniżej implementacja powyższego podejścia:
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>
Wyjście
6 3
Złożoność czasowa: O(N * D) gdzie D to liczba różnych znaków występujących w ciągu, a N to długość ciągu.
Przestrzeń pomocnicza: NA)
Utwórz quiz