Tìm chuỗi con dài nhất chứa các nguyên âm với số lượng chẵn trong C ++

Giả sử chúng ta có chuỗi s, chúng ta phải tìm kích thước của chuỗi con dài nhất chứa mỗi nguyên âm một số lần chẵn. Nghĩa là, 'a', 'e', ​​'i', 'o' và 'u' phải xuất hiện một số lần chẵn. Vì vậy, nếu chuỗi giống như "helloworld", thì đầu ra sẽ là 8.

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

• ret:=0, xác định hai bản đồ m và cnt, đặt m [“00000”]:=-1

• lưu trữ các nguyên âm vào mảng nguyên âm

• cho tôi trong phạm vi từ 0 đến kích thước của s

  • x:=s [i] và ok:=false

  • tăng cnt [x] lên 1, đặt temp:=chuỗi trống

  • cho k trong phạm vi từ 0 đến 4:temp:=temp + ‘0’ + cnt [nguyên âm [k]] mod 2

  • nếu m có nhiệt độ thì ret:=max của ret và i - m [temp], nếu không thì m [temp]:=i

• trả lại ret

Ví dụ (C ++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findTheLongestSubstring(string s) {
      int ret = 0;
      map <string, int> m;
      map <char, int> 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