# 算法设计：每个字符数为k的子字符串数

2021年4月10日12:38:43 发表评论 505 次浏览

## 本文概述

``````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``````

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

``````//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.
?>``````

``````6
3`````` 