本文概述
- C++
- Java
- Python3
- C#
例子:
【长度为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)
推荐阅读
- Python字符串find()用法详细示例
- 高级算法(模式搜索的KMP算法详细实现)
- Newgen软件设计工程师面试经验(校外)
- C和C++之间有什么区别(有哪些区别?)
- 所有Y大小子数组中最大和最小元素之间的最小差异
- 算法设计(跳转搜索算法原理解析和实现)
- 设计和实现特殊的栈数据结构|添加了空间优化版本
- 允许向左/向右/向下和向上移动的最小成本路径
- 算法题(将一个数组拆分成两个相等的和子数组)