Số lượng nguyên âm tối đa trong chuỗi con độ dài K (Maximum Number of Vowels in a Substring of Given Length) trong C++

Cho chuỗi s và số nguyên k. Tìm số lượng nguyên âm (a,e,i,o,u) lớn nhất trong mọi chuỗi con độ dài k.

Ví dụ

Đầu vào: s = "abciiidef", k = 3
Đầu ra: 3 (chuỗi con "iii").

Thuật toán cửa sổ trượt kích thước cố định

1. Khởi tạo tập hợp nguyên âm set<char>.
2. Tính số nguyên âm trong cửa sổ đầu tiên [0, k-1].
3. Trượt cửa sổ: mỗi bước bỏ s[i-k], thêm s[i], cập nhật đếm.
4. Theo dõi giá trị lớn nhất.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> vowels = {'a','e','i','o','u'};
        int cnt = 0;
        for (int i = 0; i < k; ++i) if (vowels.count(s[i])) ++cnt;
        int ans = cnt;
        for (int i = k; i < s.size(); ++i) {
            if (vowels.count(s[i-k])) --cnt;
            if (vowels.count(s[i])) ++cnt;
            ans = max(ans, cnt);
        }
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt chuỗi một lần.
• Không gian: O(1) - tập hợp nguyên âm kích thước cố định 5.

Kết quả kiểm thử

Đầu vào: "abciiidef", 3
Đầu ra: 3