算法设计（每个字符数为k的子字符串数） _字符数为k的子字符串数

本文概述

C ++
Java
Python 3
C#
的PHP

给定一个字符串和一个整数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 < bits/stdc++.h> using namespace std; const int MAX_CHAR = 26; //Returns true if all values //in freq[] are either 0 or k. bool check( int freq[], int k) { for ( int 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 int substrings(string s, int k) { int res = 0; //Initialize result//Pick a starting point for ( int i = 0; s[i]; i++) {//Initialize all frequencies as 0 //for this starting point int freq[MAX_CHAR] = { 0 }; //One by one pick ending points for ( int j = i; s[j]; 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 int main() { string s = "aabbcc" ; int k = 2; cout < < substrings(s, k) < < endl; s = "aabbc" ; k = 2; cout < < substrings(s, k) < < endl; }

Java

//Java program to count number of substrings //with counts of distinct characters as k. 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

Python 3

# 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 + = 1return 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

< ?php //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_CHAR , NULL); //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. ?>

【算法设计（每个字符数为k的子字符串数）】输出如下：