C++에서 부분 문자열의 최대 발생 횟수

문자열 s가 있다고 가정하고 다음 규칙을 충족하는 하위 문자열의 최대 발생 횟수를 찾아야 합니다. -

• 하위 문자열의 고유 문자 수는 maxLetters보다 작거나 같아야 합니다.
• 하위 문자열 크기는 minSize 및 maxSize 범위에 있어야 합니다.

따라서 입력이 "aababcaab", maxLetters =2, minSize =3 및 maxSize =4와 같으면 출력은 2가 됩니다. 하위 문자열 "aab"는 원래 문자열에서 2번 발생합니다. 이것은 2개의 고유한 문자와 3개의 크기(minSize와 maxSize 사이)라는 조건을 충족합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 지도 정의
• minSize ~ maxSize 범위의 sz
  • 지도 만들기 x, 임시 만들기, 처음에는 비어 있음
  • 0 ~ sz – 1 범위의 i용
    • x[s[i]] 1씩 증가
    • temp :=temp + s[i]
  • j가 0인 경우 범위 sz에서 s – 1까지의 i, i와 j를 1만큼 증가
    • x <=maxLetters의 크기인 경우 m[temp]를 1 증가
    • x[temp[0]] 1 감소
    • x[temp[0]]가 0이면 x에서 temp[0] 삭제
    • temp 자체에서 temp의 첫 번째 및 두 번째 요소 삭제
    • x[s[i]] 1씩 증가
    • temp :=temp + s[i]
  • x <=maxLetters의 크기인 경우 m[temp]를 1 증가
• ans :=0
• map m에 몇 가지 요소가 있는 동안
  • ans :=ans의 최대값과 i번째 키-값 쌍의 값
• 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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));
}

입력

"aababcaab"
2
3
4

출력

2