파이썬에서 부분 문자열의 0의 개수의 2배가 부분 문자열의 1의 개수의 3배보다 작거나 같은 부분 문자열의 길이를 찾는 프로그램

<시간/>

문자열과 정수 k가 주어졌다고 가정합니다. 문자열은 k 번 반복되고 다른 문자열로 만들어집니다. 우리의 임무는 2 *(하위 문자열의 0의 수) <=3 *(하위 문자열의 1의 수)인 새 문자열에서 하위 문자열의 길이를 찾는 것입니다.

따라서 입력이 k =2, input_str ='0101011'인 경우 출력은 14가 됩니다.

문자열의 길이는 7입니다. 따라서 첫 번째 문자열에서 만든 새 문자열은 01010110101011입니다. 여기서 0의 개수는 6이고 1의 개수는 8입니다. 따라서 2 * 6 <=3 * 8입니다. 따라서 가장 큰 부분 문자열은 길이가 14인 전체 문자열입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

str_len :=input_str의 크기
list_a :=0으로 초기화된 새로운 크기 목록(str_len + 1)
list_b :=0으로 초기화된 새로운 크기 목록(str_len + 1)
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)로 구성된 새로운 쌍
목록 정렬_b
temp_list :=0으로 초기화된 새로운 크기 목록(str_len + 1)
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 :=(-v + 1, 0) 쌍이 정렬된 순서를 유지하면서 삽입될 수 있는 list_b의 위치 - 1
- res :=최대 (res, temp_list[b] - i + a * str_len)
반환 결과

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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'