Tìm chuỗi con dài nhất chứa nguyên âm số lần chẵn trong C++

Cho chuỗi s, tìm độ dài chuỗi con dài nhất chứa mỗi nguyên âm ('a','e','i','o','u') số lần chẵn. VD: "helloworld" -> kết quả 8.

Giải pháp:

• ret := 0, hai map m và cnt, m["00000"] := -1
• Lưu nguyên âm vào mảng vowels
• Duyệt i từ 0 đến độ dài s:
  • x := s[i], ok := false
  • Tăng cnt[x], temp := chuỗi rỗng
  • Với k từ 0 đến 4: temp += '0' + cnt[vowels[k]] % 2
  • Nếu m có temp: ret = max(ret, i - m[temp]), ngược lại m[temp] = i
• Trả về ret

Ví dụ (C++)

#include 
using namespace std;
class Solution {
public:
    int findTheLongestSubstring(string s) {
        int ret = 0;
        map m;
        map cnt;
        m["00000"] = -1;
        char vowels[5] = {'a','e','i','o','u'};
        for(int i = 0; i < s.size(); i++){
            char x = s[i];
            bool ok = false;
            cnt[x]++;
            string temp = "";
            for(int k = 0; k < 5; k++){
                temp += ('0' + (cnt[vowels[k]] % 2));
            }
            if(m.count(temp)){
                ret = max(ret, i - m[temp]);
            }
            else{
                m[temp] = i;
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.findTheLongestSubstring("helloworld"));
}

Đầu vào

"helloworld"

Đầu ra

8