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

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

本文概述

给定一个字符串和一个整数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 + = 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

时间复杂度：O(n^2), 其中n是输入字符串的长度。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: