Chương trình tìm độ dài chuỗi con dài nhất có số lượng nguyên âm chẵn trong Python

Cho một chuỗi s (chỉ chứa chữ thường), tìm độ dài chuỗi con dài nhất mà trong đó mỗi nguyên âm (a, e, i, o, u) xuất hiện số lần chẵn.

Ví dụ: s = "anewcoffeepot" → kết quả là 10. Chuỗi con "wcoffeepot" chứa nguyên âm 'o' và 'e', mỗi nguyên âm xuất hiện 2 lần (số chẵn).

Giải thuật (Bitmask + Prefix XOR)

Sử dụng một bitmask 5 bit để biểu thị tính chẵn/lẻ của 5 nguyên âm. Bit i = 1 nghĩa là nguyên âm tương ứng xuất hiện số lẻ lần, 0 là số chẵn lần.

• Ánh xạ nguyên âm: {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}.
• Khởi tạo prefix = {0: -1} (mask 0 tại vị trí -1), mask = 0, res = 0.
• Duyệt qua chuỗi với chỉ số i:
  • Nếu s[i] là nguyên âm, lật bit tương ứng: mask ^= (1 << vowels[s[i]]).
  • Nếu mask chưa có trong prefix, lưu prefix[mask] = i.
  • Ngược lại, cập nhật res = max(res, i - prefix[mask]).
• Trả về res.

Mã nguồn Python

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))  # Output: 10

Đầu vào

"anewcoffeepot"

Đầu ra

10