โปรแกรมค้นหาความยาวของสตริงย่อยที่ยาวที่สุดด้วย 1 วินาทีในสตริงไบนารีหลังจาก 0-flip หนึ่งรายการใน Python

สมมติว่าเรามีสตริงไบนารี s เราได้รับอนุญาตให้พลิกค่าจาก "0" ถึง "1" ได้ไม่เกินหนึ่งค่า เราต้องหาความยาวของสตริงย่อยที่ต่อเนื่องกันที่ยาวที่สุดคือ 1 วินาที

ดังนั้น หากอินพุตเป็น s ="1010110001" ผลลัพธ์จะเป็น 4 ราวกับว่าเราพลิกค่าศูนย์ที่ดัชนี 3 เราก็จะได้สตริง "1011110001" โดยที่ความยาวของสตริงย่อยที่ยาวที่สุดของ 1s คือ 4 .

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ s
• แทน :=0, อัน :=0, ซ้าย :=0, ขวา :=0
• ขณะขวา
• ถ้า s[right] เหมือนกับ "1" แล้ว
  • อัน :=อัน + 1
• ในขณะที่ขวา - ซ้าย + 1 - คน> 1 ทำ
  • ลบ :=s[ซ้าย]
  • ถ้าการลบเหมือนกับ "1" แล้ว
    • อัน :=อัน - 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"

ผลลัพธ์

4