Python에서 한 쌍의 비트를 교환한 후 가장 긴 수의 1을 찾는 프로그램

<시간/>

이진 문자열 s가 있다고 가정합니다. 문자열에서 최대 한 쌍의 문자를 교환할 수 있다면 가장 긴 연속 부분 문자열인 1의 결과 길이를 찾아야 합니다.

따라서 입력이 s ="1111011111"과 같으면 출력은 9가 됩니다. s[4]와 s[9]를 바꿔 9개의 연속적인 1을 얻을 수 있기 때문입니다.

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

l :=0, cnt :=0, ans :=0
0에서 s 크기의 범위에 있는 r에 대해 다음을 수행합니다.
- cnt :=cnt + (s[r]이 "0"일 때 1, 그렇지 않으면 0)
- cnt> 1이면
  - cnt :=cnt - (s[l]이 "0"일 때 1, 그렇지 않으면 0)
  - l :=l + 1
- ans :=ans 및 (r - l + 1)의 최대값
최소값을 반환하고 s에서 1의 발생

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

예시

class Solution:
   def solve(self, s):
      l = 0
      cnt = 0
      ans = 0
      for r in range(len(s)):
         cnt += s[r] == "0"
         if cnt > 1:
            cnt -= s[l] == "0"
            l += 1
         ans = max(ans, r - l + 1)
      return min(ans, s.count("1"))
ob = Solution()
s = "1111011111"
print(ob.solve(s))

입력

"1111011111"