Python에서 한 번 0 뒤집은 후 이진 문자열에서 1로 가장 긴 부분 문자열의 길이를 찾는 프로그램

<시간/>

이진 문자열 s가 있다고 가정합니다. 최대 하나의 "0"을 "1"로 뒤집을 수 있으며 1의 가장 긴 연속 부분 문자열의 길이를 찾아야 합니다.

따라서 입력이 s ="1010110001"과 같으면 출력은 4가 됩니다. 마치 인덱스 3에 있는 0을 뒤집은 것처럼 문자열 "1011110001"을 얻습니다. 여기서 1의 가장 긴 부분 문자열의 길이는 4입니다. .

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

n :=s의 크기
an :=0, 일 :=0, 왼쪽 :=0, 오른쪽 :=0
오른쪽
s[right]가 "1"과 같으면
- 일 :=일 + 1
오른쪽 - 왼쪽 + 1 - 일> 1 동안 do
- 제거 :=s[왼쪽]
- 제거가 "1"과 같으면
  - ones :=ones - 1
- 왼쪽 :=왼쪽 + 1
ans :=ans의 최대값 및 (오른쪽 - 왼쪽 + 1)
오른쪽 :=오른쪽 + 1

반환

예시

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

def solve(s):
   n = len(s)
   ans = ones = left = right = 0
   while right < n:
      if s[right] == "1":
         ones += 1
      while right - left + 1 - ones > 1:
         remove = s[left]
         if remove == "1":
            ones -= 1
         left += 1
      ans = max(ans, right - left + 1)
      right += 1
   return ans

s = "1010110001"
print(solve(s))

입력

"1010110001"