用 Python 编写程序，找出子字符串的长度，其中子字符串中 0 的数量的两倍小于或等于子字符串中 1 的数量的三倍

pythonserver side programmingprogramming更新于 2026/1/26 11:56:17

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

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

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

为了解决这个问题，我们将遵循以下步骤 −

str_len := size of input_str
list_a := 一个大小为 (str_len + 1) 的新列表，初始化为 0
list_b := 一个大小为 (str_len + 1) 的新列表，初始化为 0
list_b[0] := 一个包含 (0, 0) 的新对
对于 0 到 str_len 范围内的 i，执行
- list_a[i + 1] := list_a[i] - 3 *(如果 input_str[i] 与 '1' 相同，则为 1，否则为 0) + 2 *(如果 input_str[i] 与 '0' 相同，则为 1，否则为 0)
- list_b[i + 1] := 一个由 (list_a[i + 1], i + 1) 组成的新对
对列表进行排序list_b
temp_list := 一个大小为 (str_len + 1) 的新列表，用 0 初始化
temp_list[0] := list_b[0, 1]
对于范围在 0 到 str_len 内的 i，执行
- temp_list[i + 1] = (temp_list[i], list_b[i + 1, 1]) 的最大值
res := 0
对于范围在 0 到 str_len 内的 i，执行
- 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]) 的底值) 的最小值
- v := a * list_a[str_len] - list_a[i]
- b := (list_b 中可以插入对 (-v + 1, 0) 的位置，同时保持排序顺序) - 1
- res := (res, temp_list[b] - i + a * str_len) 的最大值
返回 res

示例

让我们看看下面的实现以便更好地理解 −

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'))