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

สมมติว่าเรามีสตริง s (ตัวพิมพ์เล็ก) เราต้องหาความยาวของสตริงย่อยที่ยาวที่สุดโดยที่แต่ละสระเกิดขึ้นเป็นจำนวนเท่ากัน

ดังนั้น หากอินพุตเป็น s ="anewcoffeepot" ผลลัพธ์จะเป็น 10 เนื่องจากสตริงย่อย "wcoffeepot" มีสระสองตัว "o" และ "e" ซึ่งเกิดขึ้นสองครั้ง

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

• สระ :=แผนที่กำหนดสระและค่าตัวเลขเป็น {a:0, e:1, i:2, o:3, u:4}

• คำนำหน้า :=แผนที่ว่างและใส่คู่คีย์-ค่า (0, −1) เข้าไป

• หน้ากาก :=0, n :=ขนาดของ s, res :=0

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • ถ้า s[i] เป็นสระแล้ว

    • หน้ากาก :=หน้ากาก XOR (2^สระ[s[i]])

  • หากหน้ากากไม่มีคำนำหน้า

    • คำนำหน้า[หน้ากาก] :=ฉัน

  • มิฉะนั้น

    • res :=สูงสุดของ res และ (i − prefix[mask])

• ผลตอบแทน

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

ตัวอย่าง

class Solution:
   def solve(self, s):
      vowels = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
      prefix = {0: −1}
      mask = 0
      n = len(s)
      res = 0
      for i in range(n):
         if s[i] in vowels:
            mask ^= 1 << vowels[s[i]]
         if mask not in prefix:
            prefix[mask] = i
         else:
            res = max(res, i − prefix[mask])
      return res
ob = Solution()
s = "anewcoffeepot"
print(ob.solve(s))

อินพุต

"anewcoffeepot"

ผลลัพธ์

10