问题描述
我们可以用蛮力解决这个问题，获取所有可能的子字符串，并检查设置的位数是否大于n.
We could solve this question in brute force, taking all possible substrings and checking if the set bit count is greater n.
我被要求在o(n)中解决这个问题.我在o(n)中找不到任何可以解决这个问题的答案.
I was asked to solve this in o(n). I could not find any answer which could achieve this in o(n).
是否有可能在0(n)中获得二进制字符串的所有可能的子字符串?
Is it possible to get all possible substrings of binary string in 0(n)?
推荐答案
答案已更改(在问题陈述中注意到 >=).
Answer changed (noticed >= in problem statement).
制作两个索引-left和right.
我们要考虑从位置left开始至少包含k ones的子字符串.
We want to account substrings starting from position left containing at least k ones.
首先移动right，直到位数达到k.
At first move right until bit count reaches k.
现在，我们有一些好"的提示了.子字符串从left开始并在right之后的任何位置结束，因此我们可以在结果中添加len(s) - right + 1.
Now we have some "good" substrings starting at left and ending in any position after right, so we can add len(s) - right + 1 to result.
将left递增1，直到下一个one.
Increment left by 1 until the next one.
重复移动right，依此类推.算法是线性的.
Repeat moving right and so on. Algorithm is linear.
Python示例:
s = '0010110010'
#s = '110010110010'
k = 2
left = 0
right = 0
res = 0
cnt = 0
while right < len(s):
while (right < len(s)) and (cnt < k):
if s[right] == "1":
cnt += 1
right +=1
while (left <= right) and (cnt >= k):
addend = len(s) + 1 - right
res += addend
print(left, right, addend, res) #intermediate debug output
if s[left] == "1":
cnt -= 1
left +=1
print(res)
0 5 6 6
1 5 6 12
2 5 6 18
3 6 5 23
4 6 5 28
5 9 2 30
30
这篇关于给定二进制字符串"10110".查找所有子串的计数，其中设置位数=> n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！