Chương trình tìm số 1s dài nhất sau khi hoán đổi một cặp bit trong Python

Giả sử chúng ta có một chuỗi nhị phân s. Nếu chúng ta có thể hoán đổi nhiều nhất một cặp ký tự trong chuỗi, chúng ta phải tìm độ dài kết quả của chuỗi con liền kề dài nhất là 1s.

Vì vậy, nếu đầu vào là s =​​"1111011111", thì đầu ra sẽ là 9, vì chúng ta có thể hoán đổi s [4] và s [9] để được 9 giây 1 liên tiếp.

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

• l:=0, cnt:=0, ans:=0
• đối với r trong phạm vi từ 0 đến kích thước của s, thực hiện
  • cnt:=cnt + (1 khi s [r] giống với "0" nếu không thì 0)
  • nếu cnt> 1, thì
    • cnt:=cnt - (1 khi s [l] giống với "0" nếu không thì 0)
    • l:=l + 1
  • ans:=tối đa ans và (r - l + 1)
• trả về số ans tối thiểu và số lần xuất hiện là 1 trong s

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

Ví dụ

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

Đầu vào

"1111011111"

Đầu ra

9