文字列と整数 k を指定すると、すべての異なる文字が正確に k 回出現する部分文字列の数が求められます。
例:
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
素朴なアプローチ: アイデアは、すべての部分文字列を走査することです。選択した点から始まるすべての部分文字列をトラバースする開始点を修正し、すべての文字の頻度を増加させ続けます。すべての周波数が k になった場合、結果をインクリメントします。いずれかの周波数のカウントが k を超えた場合、中断して開始点を変更します。
上記のアプローチの実装を以下に示します。
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>
出力
6 3
時間計算量: O(n*n) ここで、n は入力文字列の長さです。関数 Check() は 0 から MAX_CHAR (つまり、常に 26) までの一定長のループを実行しているため、この関数 check() は O(MAX_CHAR) 時間で実行され、時間計算量は O(MAX_CHAR*n*n)=O(n^2) となります。
補助スペース: ○(1)
効率的なアプローチ: 非常に注意深く観察すると、Ktimes i forall iisin[1 D] 長さの部分文字列についても同じことをチェックするだけで十分であることがわかります。ここで D は、指定された文字列内に存在する個別の文字の数です。
口論：
長さ「p」の部分文字列 S_{i+1}S_{i+2}dots S_{i+p} について考えます。この部分文字列に 'm' 個の異なる文字があり、それぞれの異なる文字が正確に 'K' 回出現する場合、部分文字列 'p' の長さは p = Ktimes m で求められます。指定された文字列に対して「p 」は常に「K」と 1le mle 26 の倍数であるため、長さが「K」で割り切れる、m 1 le m le 26 個の異なる文字を持つ部分文字列を反復処理するだけで十分です。スライディング ウィンドウを使用して、固定長の部分文字列を反復処理します。
解決：
- 指定された文字列内に存在する個別の文字の数を見つけます。 Dとしましょう。
- 各ファイル D に対して次の操作を実行します。
- スライディング ウィンドウを使用して、長さ $i に K$ を掛けた部分文字列を反復処理します。
- 条件を満たしているかどうかを確認します - 部分文字列内のすべての個別の文字が正確に K 回出現します。
- 条件を満たす場合、カウントが増加します。
上記のアプローチの実装を以下に示します。
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>
出力
6 3
時間計算量: O(N * D) ここで、D は文字列内に存在する個別の文字の数、N は文字列の長さです。
補助スペース: の上）
クイズの作成