Số nguyên âm tối đa trong một chuỗi con có độ dài cho trước trong C ++

Giả sử chúng ta có một chuỗi s và một số nguyên k. Chúng ta phải tìm số lượng chữ cái nguyên âm tối đa trong bất kỳ chuỗi con nào của s có độ dài k.

Vì vậy, nếu đầu vào là s =​​"abciiidef", k =3, thì đầu ra sẽ là 3

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

• cnt:=0

• Xác định một bộ m

• đối với mỗi nguyên âm v, làm

  • chèn v vào m

• ret:=0

• để khởi tạo i:=0, khi i

  • cnt:=cnt + (1 khi s [i] tính bằng m, ngược lại là 0)

• ret:=tối đa của ret và cnt

• n:=kích thước của s

• để khởi tạo i:=k, khi i

  • nếu s [i - k] là thành viên của m thì -

    • (giảm cnt đi 1)

  • cnt:=cnt + (1 khi s [i] tính bằng m, ngược lại là 0)

  • ret:=tối đa của ret và cnt

• trả lại ret

Ví dụ

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 maxVowels(string s, int k) {
      int cnt = 0;
      set<char> m;
      for (auto it : { 'a', 'e', 'i', 'o', 'u' })
      m.insert(it);
      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;
   }
};
main(){
   Solution ob;
   cout << (ob.maxVowels("abciiidef",3));
}

Đầu vào

"abciiidef",3

Đầu ra

3