Given a binary string of length N and an integer K, we need to find out how many substrings of this string are exist which contains exactly K ones.
Examples:
Input : s = “10010”
K = 1
Output : 9
The 9 substrings containing one 1 are,
“1”, “10”, “100”, “001”, “01”, “1”,
“10”, “0010” and “010”
static int countOfSubstringWithKOnes(
String s, int K)
{
int N = s.length();
int res = 0;
int countOfOne = 0;
int []freq = new int[N+1];
freq[0] = 1;
for (int i = 0; i < N; i++) {
countOfOne += (s.charAt(i) - '0');
if (countOfOne >= K) {
res += freq[countOfOne - K];
}
freq[countOfOne]++;
}
return res;
}
注意：求子串的时候，尤其是涉及长度，子串里面元素个数之类的问题，可以用类似于动态规划的方法，用当前遍历的值减去之前的值，来找子串，实现复杂度O(n)。
相似的问题：https://www.geeksforgeeks.org/longest-substring-with-count-of-1s-more-than-0s/
