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

本文概述

  • C++
  • Java
  • Python3
  • C#
给定一个字符串str小写字母和一个整数?, 任务是计算所有长度的子串?完全有?不同的字符。
例子:
【长度为K的子字符串的计数,其中恰好有K个不同的字符】输入: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)

    推荐阅读