โปรแกรมหาความยาวของสตริงย่อยที่สระทุกตัวปรากฏจำนวนคู่ใน Python

สมมติว่าเรามีสตริง s (ตัวพิมพ์เล็ก) เราต้องการหาความยาวของสตริงย่อยที่สระเสียง (a, e, i, o, u) ทุกตัวปรากฏจำนวนคู่ (even number of times)

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

ขั้นตอนการแก้ปัญหา (ใช้ Bitmask + Prefix)

• สร้างแมพ vowels กำหนดค่าบิตให้สระ: {a:0, e:1, i:2, o:3, u:4}
• สร้าง prefix แมพว่าง และใส่คู่ (0, -1) เข้าไป
• กำหนด mask = 0, n = len(s), res = 0
• วนลูป i ตั้งแต่ 0 ถึง n-1:
  • ถ้า s[i] เป็นสระ ให้ mask := mask XOR (2^vowels[s[i]])
  • ถ้า mask ไม่อยู่ใน prefix ให้ prefix[mask] := i
  • มิฉะนั้น ให้ res := max(res, i - prefix[mask])
• คืนค่า res

ตัวอย่างโค้ด

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