Chương trình tìm độ dài của chuỗi con dài nhất với 1s trong chuỗi nhị phân sau một lần lật 0 bằng Python

Giả sử chúng ta có một chuỗi nhị phân s. Chúng tôi được phép lật nhiều nhất một "0" thành "1", chúng tôi phải tìm độ dài của chuỗi con liền kề dài nhất là 1s.

Vì vậy, nếu đầu vào là s =​​"1010110001", thì đầu ra sẽ là 4, như nếu chúng ta lật số 0 ở chỉ số 3, thì chúng ta nhận được chuỗi "1011110001", ở đây độ dài của chuỗi con dài nhất của 1s là 4 .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s
• ans:=0, ones:=0, left:=0, right:=0
• trong khi đúng
• nếu s [right] giống như "1", thì
  • cái:=cái + 1
• trong khi phải - trái + 1 - những cái> 1, thực hiện
  • loại bỏ:=s [left]
  • nếu loại bỏ giống như "1", thì
    • cái:=cái - 1
  • left:=left + 1
• ans:=tối đa ans và (phải - trái + 1)
• right:=right + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

"1010110001"

Đầu ra

4