จำนวนสระสูงสุดใน Substring ความยาว K ใน C++

สมมติว่าเรามีสตริง s และจำนวนเต็ม k เราต้องหาจำนวนสระ (vowel) สูงสุดใน substring ใดๆ ของ s ที่มีความยาว k

ตัวอย่าง: s = "abciiidef", k = 3 ผลลัพธ์ = 3

วิธีแก้ปัญหา (Sliding Window)

1. นับสระใน window แรก k ตัว
2. เลื่อน window ทีละตัว:
   • ลบสระที่ออกจาก window (i-k)
   • บวกสระที่เข้ามา (i)
   • อัปเดตค่าสูงสุด
3. เวลา O(n), พื้นที่ O(1)

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

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

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

int main(){ 
    Solution ob; 
    cout << (ob.maxVowels("abciiidef",3)); 
}

ข้อมูลนำเข้า

"abciiidef",3

ผลลัพธ์

3