Chương trình tìm độ dài của chuỗi con dài nhất với số nguyên âm chẵn bằng Python

Giả sử chúng ta có một chuỗi s (chữ thường), chúng ta phải tìm độ dài của chuỗi con dài nhất mà mỗi nguyên âm xuất hiện với số lần chẵn.

Vì vậy, nếu đầu vào là s =​​"anewcoffeepot", thì đầu ra sẽ là 10, vì chuỗi con "wcoffeepot" có hai nguyên âm "o" và "e", cả hai đều xuất hiện hai lần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nguyên âm:=một bản đồ gán các nguyên âm và giá trị số dưới dạng {a:0, e:1, i:2, o:3, u:4}

• prefix:=một bản đồ trống và chèn một cặp khóa-giá trị (0, −1) vào đó

• mask:=0, n:=size of s, res:=0

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • nếu s [i] là một nguyên âm thì

    • mask:=mask XOR (2 ^ nguyên âm [s [i]])

  • nếu mặt nạ không ở tiền tố, thì

    • tiền tố [mask]:=i

  • nếu không,

    • res:=tối đa res và (i - tiền tố [mask])

• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

"anewcoffeepot"

Đầu ra

10