Cho chuỗi s chỉ chứa nguyên âm tiếng Anh. Tìm độ dài substring "đẹp" (beautiful) dài nhất. Điều kiện: (1) Có đủ 5 nguyên âm a,e,i,o,u. (2) Các chữ cái theo thứ tự bảng chữ cái (a→e→i→o→u). Không có → trả 0.
Ví dụ: s = "aaioaaaaeiiouuooaauu" → output = 10 (substring "aaaaeiiouu").
Giải thuật (Two-pointer scan theo nhóm nguyên âm)
- vowels = ['a','e','i','o','u'].
- Duyệt l từ 0: với mỗi vowel theo thứ tự, kiểm tra s[r] == vowel và đếm run-length.
- Nếu đủ 5 vowel liên tiếp theo thứ tự → cập nhật longest = max(longest, r-l).
- Nhảy l = r, tiếp tục.
Code Python
def solve(s):
vowels = ['a', 'e', 'i', 'o', 'u']
l, r, longest = 0, 0, 0
while l < len(s):
valid = True
for vowel in vowels:
valid &= (r < len(s) and s[r] == vowel)
while r < len(s) and s[r] == vowel:
r += 1
if valid:
longest = max(longest, r - l)
l = r
return longest
s = "aaioaaaaeiiouuooaauu"
print(solve(s)) # 10
Đầu vào / Đầu ra
Input: "aaioaaaaeiiouuooaauu"
Output: 10