长度为K的子字符串的计数，其中恰好有K个不同的字符

2021年4月15日17:26:38 发表评论 848 次浏览

本文概述

给定一个字符串str小写字母和一个整数ķ, 任务是计算所有长度的子串ķ完全有ķ不同的字符。

例子：

输入：str =" abcc", K = 2
输出：2
说明：
长度为K = 2的可能子串是
ab：2个不同的字符
bc：2个不同的字符
cc：1个不同的字符
仅存在两个有效的子字符串{" ab", "bc"}。
输入：str =" aabab", K = 3
输出：0
说明：可能的长度为K = 3的子字符串是
aab：2个不同的字符
aba：2个不同的字符
bab：2个不同的字符
不存在长度为3的子字符串, 其中只有3个不同的字符

简单的方法：

其思想是生成长度为K的所有子字符串，并为每个子字符串计数不同字符的数量。如果一个字符串的长度为N，那么可以有N - K + 1个长度为K的子字符串。生成这些子字符串需要O(N)复杂度，检查每个子字符串需要O(K)复杂度，因此使总体复杂度为O(N*K)。

有效的方法：

这个想法是使用窗口滑动技术。维护一个大小为K的窗口，并使用HashMap保存窗口中所有字符的计数。遍历字符串，减少前一个窗口的第一个字符的计数，并在HashMap中添加当前窗口的最后一个字符的频率。如果长度为K的窗口中不同字符的计数等于K，则将答案增加1。

下面是上述方法的实现：

C++

//C++ program to find the 
//count of k length substrings 
//with k distinct characters 
//using sliding window 
#include <bits/stdc++.h> 
using namespace std; 
  
//Function to return the 
//required count of substrings 
int countSubstrings(string str, int K) 
{ 
     int N = str.size(); 
     //Store the count 
     int answer = 0; 
  
     //Store the count of 
     //distinct characters 
     //in every window 
     unordered_map<char , int> map; 
  
     //Store the frequency of 
     //the first K length substring 
     for ( int i = 0; i <K; i++) { 
  
         //Increase frequency of 
         //i-th character 
         map[str[i]]++; 
     } 
  
     //If K distinct characters 
     //exist 
     if (map.size() == K) 
         answer++; 
  
     //Traverse the rest of the 
     //substring 
     for ( int i = K; i <N; i++) { 
  
         //Increase the frequency 
         //of the last character 
         //of the current substring 
         map[str[i]]++; 
         //Decrease the frequency 
         //of the first character 
         //of the previous substring 
         map[str[i - K]]--; 
  
         //If the character is not present 
         //in the current substring 
         if (map[str[i - K]] == 0) { 
             map.erase(str[i - K]); 
         } 
  
         //If the count of distinct 
         //characters is 0 
         if (map.size() == K) { 
             answer++; 
         } 
     } 
  
     //Return the count 
     return answer; 
} 
  
//Driver code 
int main() 
{ 
     //string str 
     string str = "aabcdabbcdc" ; 
  
     //integer K 
     int K = 3; 
  
     //Print the count of K length 
     //substrings with k distinct characters 
     cout <<countSubstrings(str, K) <<endl; 
  
     return 0; 
}

Java

//Java program to find the count 
//of k length substrings with k 
//distinct characters using 
//sliding window 
import java.util.*; 
  
class GFG{ 
  
//Function to return the 
//required count of substrings 
public static int countSubstrings(String str, int K) 
{ 
     int N = str.length(); 
      
     //Store the count 
     int answer = 0 ; 
  
     //Store the count of 
     //distinct characters 
     //in every window 
     Map<Character, Integer> map = new HashMap<Character, Integer>(); 
  
     //Store the frequency of 
     //the first K length substring 
     for ( int i = 0 ; i <K; i++) 
     { 
          
         //Increase frequency of 
         //i-th character 
         if (map.get(str.charAt(i)) == null ) 
         { 
             map.put(str.charAt(i), 1 ); 
         } 
         else
         { 
             map.put(str.charAt(i), map.get(str.charAt(i)) + 1 ); 
         } 
     } 
  
     //If K distinct characters 
     //exist 
     if (map.size() == K) 
         answer++; 
  
     //Traverse the rest of the 
     //substring 
     for ( int i = K; i <N; i++) 
     { 
  
         //Increase the frequency 
         //of the last character 
         //of the current substring 
         if (map.get(str.charAt(i)) == null ) 
         { 
             map.put(str.charAt(i), 1 ); 
         } 
         else
         { 
             map.put(str.charAt(i), map.get(str.charAt(i)) + 1 ); 
         } 
          
         //Decrease the frequency 
         //of the first character 
         //of the previous substring 
         map.put(str.charAt(i - K), map.get(str.charAt(i - K)) - 1 ); 
  
         //If the character is not present 
         //in the current substring 
         if (map.get(str.charAt(i - K)) == 0 ) 
         { 
             map.remove(str.charAt(i - K)); 
         } 
  
         //If the count of distinct 
         //characters is 0 
         if (map.size() == K) 
         { 
             answer++; 
         } 
     } 
  
     //Return the count 
     return answer; 
} 
  
//Driver code 
public static void main(String[] args) 
{ 
      
     //string str 
     String str = "aabcdabbcdc" ; 
  
     //integer K 
     int K = 3 ; 
  
     //Print the count of K length 
     //substrings with k distinct characters 
     System.out.println(countSubstrings(str, K)); 
} 
} 
  
//This code is contributed by grand_master

Python3

# Python3 program to find the 
# count of k length substrings 
# with k distinct characters 
# using sliding window 
  
# Function to return the 
# required count of substrings 
def countSubstrings( str , K): 
  
     N = len ( str ) 
  
     # Store the count 
     answer = 0
  
     # Store the count of 
     # distinct characters 
     # in every window 
     map = {} 
  
     # Store the frequency of 
     # the first K length substring 
     for i in range (K): 
  
         # Increase frequency of 
         # i-th character 
         map [ str [i]] = map .get( str [i], 0 ) + 1
          
     # If K distinct characters 
     # exist 
     if ( len ( map ) = = K): 
         answer + = 1
  
     # Traverse the rest of the 
     # substring 
     for i in range (K, N): 
  
         # Increase the frequency 
         # of the last character 
         # of the current substring 
         map [ str [i]] = map .get( str [i], 0 ) + 1
          
         # Decrease the frequency 
         # of the first character 
         # of the previous substring 
         map [ str [i - K]] - = 1
  
         # If the character is not present 
         # in the current substring 
         if ( map [ str [i - K]] = = 0 ): 
             del map [ str [i - K]] 
  
         # If the count of distinct 
         # characters is 0 
         if ( len ( map ) = = K): 
             answer + = 1
  
     # Return the count 
     return answer 
  
# Driver code 
if __name__ = = '__main__' : 
      
     str = "aabcdabbcdc"
  
     # Integer K 
     K = 3
  
     # Print the count of K length 
     # substrings with k distinct characters 
     print (countSubstrings( str , K)) 
  
# This code is contributed by mohit kumar 29

C#

//C# program to find the count
//of k length substrings with k 
//distinct characters using 
//sliding window 
using System;
using System.Collections.Generic; 
  
class GFG{
  
//Function to return the 
//required count of substrings 
public static int countSubstrings( string str, int K) 
{ 
     int N = str.Length;
      
     //Store the count 
     int answer = 0; 
  
     //Store the count of 
     //distinct characters 
     //in every window 
     Dictionary<char , int> map = new Dictionary<char , int>(); 
  
     //Store the frequency of 
     //the first K length substring 
     for ( int i = 0; i <K; i++) 
     { 
          
         //Increase frequency of 
         //i-th character
         if (!map.ContainsKey(str[i]))
         {
             map[str[i]] = 1;
         }
         else
         {
             map[str[i]]++; 
         }
     } 
  
     //If K distinct characters 
     //exist 
     if (map.Count == K) 
         answer++; 
  
     //Traverse the rest of the 
     //substring 
     for ( int i = K; i <N; i++)
     { 
          
         //Increase the frequency 
         //of the last character 
         //of the current substring 
         if (!map.ContainsKey(str[i]))
         {
             map[str[i]] = 1;
         }
         else
         {
             map[str[i]]++; 
         }
          
         //Decrease the frequency 
         //of the first character 
         //of the previous substring
         map[str[i - K]]--;
  
         //If the character is not present 
         //in the current substring 
         if (map[str[i - K]] == 0)
         { 
             map.Remove(str[i - K]); 
         } 
  
         //If the count of distinct 
         //characters is 0 
         if (map.Count == K)
         { 
             answer++; 
         } 
     } 
  
     //Return the count 
     return answer; 
} 
  
//Driver code 
public static void Main( string [] args) 
{ 
      
     //string str 
     string str = "aabcdabbcdc" ; 
  
     //integer K 
     int K = 3; 
  
     //Print the count of K length 
     //substrings with k distinct characters 
     Console.Write(countSubstrings(str, K));
} 
}
  
//This code is contributed by rutvik_56

输出如下：

5

时间复杂度：O(n)

木子山

发表评论

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