สมมติว่าเรามีสตริงไบนารี s หากเราสามารถสลับอักขระได้ไม่เกินหนึ่งคู่ในสตริง เราต้องหาความยาวที่เป็นผลลัพธ์ของสตริงย่อยที่ยาวที่สุดของ 1 วินาที
ดังนั้น หากอินพุตเป็น s ="1111011111" เอาต์พุตจะเป็น 9 เนื่องจากเราสามารถสลับ s[4] และ s[9] เพื่อให้ได้ 9 1 วินาทีติดต่อกัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- l :=0, cnt :=0, ans :=0
- สำหรับ r ในช่วง 0 ถึงขนาดของ s ทำ
- cnt :=cnt + (1 เมื่อ s[r] เหมือนกับ "0" มิฉะนั้น 0)
- ถ้า cnt> 1 แล้ว
- cnt :=cnt - (1 เมื่อ s[l] เหมือนกับ "0" มิฉะนั้น 0)
- l :=l + 1
- ans :=สูงสุดของ ans และ (r - l + 1)
- คืนค่าขั้นต่ำของ ans และการเกิดขึ้นของ 1 ใน s
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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"
ผลลัพธ์
9
