โปรแกรมค้นหาสตริงย่อยที่ยาวที่สุดโดยใช้ Python

สมมติว่าเรามีสตริง s เราต้องหาสตริงย่อยที่ยาวที่สุดของ s สำหรับสตริง s จะเรียกว่า nice เมื่อสำหรับตัวอักษรทุกตัวในหน่วย s จะปรากฏเป็นตัวพิมพ์ใหญ่และตัวพิมพ์เล็กทั้งคู่ หากมีหลายสตริงย่อยดังกล่าว ให้ส่งคืนสตริงย่อยของรายการแรกสุด

ดังนั้น หากอินพุตเป็น s ="ZbybBbz" ผลลัพธ์จะเป็น "bBb" เนื่องจากมีตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ B's

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

• cur_max:=-1

• res:=สตริงว่าง

• สำหรับฉันในช่วง 0 ถึงขนาด s ทำ

  • c :=s[i]

  • บน :=ชุดใหม่

  • ล่าง :=ชุดใหม่

  • ถ้า c เป็นตัวพิมพ์เล็ก แล้ว

    • เพิ่ม c ลงในส่วนล่าง

  • ถ้า c เป็นตัวพิมพ์ใหญ่ แล้ว

    • เพิ่ม c เป็นตัวบน แต่ก่อนที่จะแปลงเป็นตัวพิมพ์เล็ก

  • สำหรับ j ในช่วง i+1 ถึงขนาด s ทำ

    • ค :=s[j]

    • ถ้า c เป็นตัวพิมพ์เล็ก แล้ว

      • เพิ่ม c ลงในส่วนล่าง

    • ถ้า c เป็นตัวพิมพ์ใหญ่ แล้ว

      • เพิ่ม c เป็นตัวบน แต่ก่อนที่จะแปลงเป็นตัวพิมพ์เล็ก

    • ถ้าตัวบนเท่ากับตัวล่างแล้ว

      • ถ้า j-i> cur_max แล้ว

        • cur_max :=j-i

        • res :=สตริงย่อยของ s[จากดัชนี i ถึง j+1]

• ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

def solve(s):
   cur_max= -1
   res=""
   for i in range(len(s)):
      c = s[i]
      upper = set()
      lower = set()
      if c.islower():
         lower.add(c)
      if c.isupper():
         upper.add(c.lower())
      for j in range(i+1,len(s)):
         c = s[j]
         if c.islower():
            lower.add(c)
         if c.isupper():
            upper.add(c.lower())
         if upper == lower:
            if j-i>cur_max:
               cur_max = j-i
               res = s[i:j+1]
   return res
s = "ZbybBbz"
print(solve(s))

อินพุต

"ZbybBbz"

ผลลัพธ์

bBb