在Python中查找子串的长度，其中子串中的0的数量是其1的数量的三倍，并且小于或等于两倍的计算机领域英语文章

假设给定一个字符串和一个整数k。该字符串重复k次并重新生成另一个字符串。我们的任务是找到新字符串中子字符串的长度，其中 2 *（子字符串中零的数量）<= 3 *（子字符串中1的数量）。

因此，如果输入为k = 2，input_str =’0101011’，则输出将为 14。

该字符串的长度为7。因此，从第一个字符串制作的新字符串为 01010110101011。这里的0的数量为6，1的数量为8。因此，2 * 6 <= 3 * 8。因此，最大子字符串是整个长度为14的字符串。

要解决此问题，请执行以下步骤−

str_len:=输入字符串大小
list_a:=大小为(str_len + 1)的新列表，初始化为0
list_b:=大小为(str_len + 1)的新列表，初始化为0
list_b [0]:=包含（0,0）的新对
for i in range 0 to str_len, do
- list_a[i+1]:=-3*（如果input_str [i]与’1’相同，则为1，否则为0）+ 2 *（如果input_str [i]与’0’相同，则为1，否则为0）+ list_a[i]
- list_b[i + 1] := 包含（list_a [i + 1]，i + 1）的新对
对列表list_b进行排序
templist :=大小为（str_len + 1）的新列表，初始化为0
templist[0]: = list_b [0,1]
for i in range 0 to str_len, do
- temp_list[i + 1] =（temp_list[i]，list_b [i + 1,1]）的最大值
res:= 0
for i in range 0 to str_len, do
- tmp:=list_b [0, 0] -list_a [i]
- 如果list_a [str_len]< =0，则
  - a:=k-1
  - 如果tmp + list_a[str_len] * a> 0，则
  - 进入下一次迭代
- 否则，当tmp> 0时，然后
  - 进入下一次迭代
- 否则，
  - a:= k-1和（（-tmp / list_a[str_len]）的floor值）的最小值
- v:=a * list_a[str_len] – list_a[i]
- b：=（可以插入新对（- v + 1,0）保持排序顺序的列表list_b中的位置）-1
- res: =最大值（res，temp_list[b] – i + a * str_len）
返回res

例子

让我们看一下以下实现，以获得更好的理解−

from bisect import bisect_left
defsolve(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'))