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