Số lần xuất hiện tối đa của một chuỗi con trong C ++

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số lần xuất hiện tối đa của bất kỳ chuỗi con nào thỏa mãn các quy tắc sau -

• Số lượng các ký tự khác nhau trong chuỗi con phải nhỏ hơn hoặc bằng maxLetters.
• Kích thước chuỗi con phải nằm trong phạm vi minSize và maxSize bao gồm cả.

Vì vậy, nếu đầu vào là - “aababcaab”, maxLetters =2, minSize =3 và maxSize =4, thì đầu ra sẽ là 2. Chuỗi con “aab” có 2 lần xuất hiện trong chuỗi ban đầu. Điều này đáp ứng các điều kiện, 2 chữ cái duy nhất và kích thước 3 (giữa minSize và maxSize).

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

• Xác định bản đồ m
• cho sz trong phạm vi minSize đến maxSize
  • tạo một bản đồ x, tạo một bản đồ tạm thời, ban đầu để trống
  • cho tôi trong phạm vi từ 0 đến sz - 1
    • tăng x [s [i]] lên 1
    • temp:=temp + s [i]
  • đối với j là 0, i trong phạm vi sz đến kích thước là s-1, tăng i và j lên 1
    • nếu kích thước x <=maxLetters, thì hãy tăng m [temp] lên 1
    • giảm x [temp [0]] đi 1
    • nếu x [temp [0]] là 0, thì hãy xóa temp [0] khỏi x
    • xóa phần tử tạm thời đầu tiên và thứ hai khỏi chính phần tử tạm thời
    • tăng x [s [i]] lên 1
    • temp:=temp + s [i]
  • nếu kích thước x <=maxLetters, thì hãy tăng m [temp] lên 1
• ans:=0
• trong khi bản đồ m có một số phần tử, thì
  • ans:=max của ans và giá trị của cặp khóa-giá trị thứ i
• trả lại ans

Ví dụ (C ++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
      unordered_map <string ,int > m;
      for(int sz = minSize; sz <= minSize; sz++){
         unordered_map <char, int> x;
         string temp ="";
         for(int i = 0; i < sz; i++){
            x[s[i]]++;
            temp += s[i];
         }
         for(int j = 0, i = sz; i < s.size(); i++, j++){
            if(x.size() <= maxLetters){
               m[temp]++;
            }
            x[temp[0]]--;
            if(x[temp[0]] == 0)x.erase(temp[0]);
            temp.erase(temp.begin(),temp.begin() + 1);
            x[s[i]]++;
            temp += s[i];
         }
         if(x.size() <= maxLetters){
            m[temp]++;
         }
      }
      int ans = 0;
      unordered_map <string ,int > :: iterator i = m.begin();
      while(i != m.end()){
         ans = max (ans, i->second);
         i++;
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.maxFreq("aababcaab",2,3,4));
}

Đầu vào

"aababcaab"
2
3
4

Đầu ra

2