Python中查找子串中零个数的两倍小于或等于子串中零个数的三倍的子串长度的程序
假设我们有一个字符串和一个整数k。该字符串重复k次并生成另一个字符串。我们的任务是找到新字符串中子字符串的长度，其中2*（子字符串中的零数）<=3*（子字符串中的1数）。
所以，如果输入像k=2,input_str='0101011'，那么输出将是14。
字符串的长度是7。所以，由第一个字符串组成的新字符串是01010110101011。这里0的数量是6，1的数量是8。所以，2*6<=3*8。因此，最大的子串是长度为14的整个串。
示例
让我们看看以下实现以获得更好的理解-
from bisect import bisect_left
def solve(k, input_str):
str_len = len(input_str)
list_a = [0] * (str_len + 1)
list_b = [0] * (str_len + 1)
list_b[0] = (0, 0)
for i in range(str_len):
list_a[i + 1] = list_a[i] - 3 * (input_str[i] == '1') + 2 * (input_str[i] == '0')
list_b[i + 1] = (list_a[i + 1], i + 1)
list_b.sort()
temp_list = [0] * (str_len + 1)
temp_list[0] = list_b[0][1]
for i in range(str_len):
temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1])
res = 0
for i in range(str_len):
tmp = list_b[0][0] - list_a[i]
if list_a[str_len] <= 0:
a = k - 1
if tmp + list_a[str_len] * a > 0:
continue
elif tmp > 0:
continue
else:
a = min(k - 1, -tmp //list_a[str_len])
v = a * list_a[str_len] - list_a[i]
b = bisect_left(list_b, (-v + 1, 0)) - 1
res = max(res, temp_list[b] - i + a * str_len)
return res
print(solve(2, '0101011'))输入
2, '0101011'输出结果
14