给定一组小写字母，计算所有可能的子字符串（不一定是不同的），这些子字符串正好有k个不同的字符。 例如：
null
Input: abc, k = 2Output: 2Possible substrings are {"ab", "bc"}Input: aba, k = 2Output: 3Possible substrings are {"ab", "ba", "aba"}Input: aa, k = 1Output: 3Possible substrings are {"a", "a", "aa"}
方法1（暴力）
如果字符串的长度为n，则可能存在n*（n+1）/2个可能的子字符串。一种简单的方法是生成所有子字符串，并检查每个子字符串是否有k个唯一字符。如果我们使用这个蛮力，需要O（n*n）来生成所有子字符串，并且O（n）对每个子字符串进行检查。因此，总的来说，它会变成O（n*n*n）。
方法2
这个问题可以用O（n*n）来解决。其思想是在生成子字符串和使用该哈希表检查唯一字符数的同时维护哈希表。 下面的实现假设输入字符串只包含从“a”到“z”的字符。 实施
C++
// C++ program to count number of substrings with // exactly k distinct characters in a given string #include<bits/stdc++.h> using namespace std; // Function to count number of substrings // with exactly k unique characters int countkDist(string str, int k) { int n = str.length(); // Initialize result int res = 0; // To store count of characters from 'a' to 'z' int cnt[26]; // Consider all substrings beginning with // str[i] for ( int i = 0; i < n; i++) { int dist_count = 0; // Initializing array with 0 memset (cnt, 0, sizeof (cnt)); // Consider all substrings between str[i..j] for ( int j=i; j<n; j++) { // If this is a new character for this // substring, increment dist_count. if (cnt[str[j] - 'a' ] == 0) dist_count++; // Increment count of current character cnt[str[j] - 'a' ]++; // If distinct character count becomes k, // then increment result. if (dist_count == k) res++; if (dist_count > k) break ; } } return res; } // Driver Program int main() { string str = "abcbaa" ; int k = 3; cout << "Total substrings with exactly " << k << " distinct characters :" << countkDist(str, k) << endl; return 0; } |
JAVA
// Java program to CountKSubStr number of substrings // with exactly distinct characters in a given string import java.util.Arrays; public class CountKSubStr { // Function to count number of substrings // with exactly k unique characters int countkDist(String str, int k) { // Initialize result int res = 0 ; int n = str.length(); // To store count of characters from 'a' to 'z' int cnt[] = new int [ 26 ]; // Consider all substrings beginning with // str[i] for ( int i = 0 ; i < n; i++) { int dist_count = 0 ; // Initializing count array with 0 Arrays.fill(cnt, 0 ); // Consider all substrings between str[i..j] for ( int j=i; j<n; j++) { // If this is a new character for this // substring, increment dist_count. if (cnt[str.charAt(j) - 'a' ] == 0 ) dist_count++; // Increment count of current character cnt[str.charAt(j) - 'a' ]++; // If distinct character count becomes k, // then increment result. if (dist_count == k) res++; } } return res; } // Driver Program public static void main(String[] args) { CountKSubStr ob = new CountKSubStr(); String ch = "abcbaa" ; int k = 3 ; System.out.println( "Total substrings with exactly " + k + " distinct characters : " + ob.countkDist(ch, k)); } } |
Python 3
# Python3 program to count number of # substrings with exactly k distinct # characters in a given string # Function to count number of substrings # with exactly k unique characters def countkDist(str1, k): n = len (str1) # Initialize result res = 0 # To store count of characters from # 'a' to 'z' cnt = [ 0 ] * 27 # Consider all substrings beginning # with str[i] for i in range ( 0 , n): dist_count = 0 # Initializing array with 0 cnt = [ 0 ] * 27 # Consider all substrings between str[i..j] for j in range (i, n): # If this is a new character for this # substring, increment dist_count. if (cnt[ ord (str1[j]) - 97 ] = = 0 ): dist_count + = 1 # Increment count of current character cnt[ ord (str1[j]) - 97 ] + = 1 # If distinct character count becomes k, # then increment result. if (dist_count = = k): res + = 1 if (dist_count > k): break return res # Driver Code if __name__ = = "__main__" : str1 = "abcbaa" k = 3 print ( "Total substrings with exactly" , k, "distinct characters : " , end = "") print (countkDist(str1, k)) # This code is contributed by # Sairahul Jella |
C#
// C# program to CountKSubStr number of substrings // with exactly distinct characters in a given string using System; public class CountKSubStr { // Function to count number of substrings // with exactly k unique characters int countkDist( string str, int k) { // Initialize result int res = 0; int n = str.Length; // To store count of characters from 'a' to 'z' int [] cnt = new int [26]; // Consider all substrings beginning with // str[i] for ( int i = 0; i < n; i++) { int dist_count = 0; // Initializing count array with 0 Array.Clear(cnt, 0,cnt.Length); // Consider all substrings between str[i..j] for ( int j=i; j<n; j++) { // If this is a new character for this // substring, increment dist_count. if (cnt[str[j] - 'a' ] == 0) dist_count++; // Increment count of current character cnt[str[j] - 'a' ]++; // If distinct character count becomes k, // then increment result. if (dist_count == k) res++; } } return res; } // Driver Program public static void Main() { CountKSubStr ob = new CountKSubStr(); string ch = "abcbaa" ; int k = 3; Console.Write( "Total substrings with exactly " + k + " distinct characters : " + ob.countkDist(ch, k)); } } |
PHP
<?php // PHP program to CountKSubStr number of substrings // with exactly distinct characters in a given string // Function to count number of substrings // with exactly k unique characters function countkDist( $str , $k ) { // Initialize result $res = 0; $n = strlen ( $str ); // To store count of characters from 'a' to 'z' $cnt = array (); // Consider all substrings beginning with // str[i] for ( $i = 0; $i < $n ; $i ++) { $dist_count = 0; // Initializing count array with 0 $cnt = array_fill (0, 0, true); // Consider all substrings between str[i..j] for ( $j = $i ; $j < $n ; $j ++) { // If this is a new character for this // substring, increment dist_count. if ( $cnt [ord( $str [ $j ]) - ord( 'a' )] == 0) $dist_count ++; // Increment count of current character $cnt [ord( $str [ $j ]) - ord( 'a' )]++; // If distinct character count becomes k, // then increment result. if ( $dist_count == $k ) $res ++; } } return $res ; } // Driver code { $ch = "abcbaa" ; $k = 3; echo ( "Total substrings with exactly " . $k . " distinct characters : " . countkDist( $ch , $k )); } // This code is contributed by Code_Mech |
Javascript
<script> // javascript program to CountKSubStr number of substrings // with exactly distinct characters in a given string // Function to count number of substrings // with exactly k unique characters function countkDist(str , k) { // Initialize result var res = 0; var n = str.length; // To store count of characters from 'a' to 'z' var cnt = Array.from({length: 26}, (_, i) => 0); // Consider all substrings beginning with // str[i] for (i = 0; i < n; i++) { var dist_count = 0; // Consider all substrings between str[i..j] for (j=i; j<n; j++) { // If this is a new character for this // substring, increment dist_count. if (cnt[str.charAt(j).charCodeAt(0) - 'a' .charCodeAt(0)] == 0) dist_count++; // Increment count of current character cnt[str.charAt(j).charCodeAt(0) - 'a' .charCodeAt(0)]++; // If distinct character count becomes k, // then increment result. if (dist_count == k) res++; } } return res; } // Driver Program var ch = "abcbaa" ; var k = 3; document.write( "Total substrings with exactly " + k + " distinct characters : " + countkDist(ch, k)); // This code contributed by shikhasingrajput </script> |
输出：
Total substrings with exactly 3 distinct characters : 8
时间复杂性： O（n*n）
空间复杂性 ：O（1） 说明：仅使用26个大小的数组，可以考虑恒定空间。
练习（进一步优化）： 上面的代码在外循环的每次迭代中重置计数数组“cnt[]”。对于较大的字母表大小，这可能非常昂贵。我们能否修改上述程序，使cnt[]不会每次重置？ 本文由 拉胡尔·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
