Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 부분 문자열의 최대 발생 횟수

문자열 s가 주어졌을 때, 다음 조건을 만족하는 임의의 부분 문자열이 나타나는 최대 횟수를 구해야 합니다.

  • 부분 문자열에 포함된 서로 다른 문자의 개수는 maxLetters 이하여야 합니다.
  • 부분 문자열의 길이는 minSize 이상 maxSize 이하 범위 안에 있어야 합니다.

예를 들어 입력이 "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4라면 결과는 2가 됩니다. 부분 문자열 "aab"는 원본 문자열 안에서 두 번 등장하며, 서로 다른 문자가 2개이고 길이가 3(minSize와 maxSize 사이)이므로 모든 조건을 충족하기 때문입니다.

접근 방법

슬라이딩 윈도우 기법과 해시맵을 활용하면 효율적으로 문제를 해결할 수 있습니다. 절차는 다음과 같습니다.

  • 부분 문자열의 등장 횟수를 저장할 맵 m을 정의합니다.
  • sz를 minSize부터 maxSize까지 반복합니다.
    참고: 실제 구현에서는 minSize만 검사해도 충분합니다. 길이가 더 긴 부분 문자열이 k번 등장한다면, 그 앞부분에 해당하는 길이 minSize짜리 부분 문자열 역시 최소 k번 등장하기 때문입니다.
  • 각 윈도우의 문자 개수를 추적할 맵 x를 만들고, 빈 문자열 temp를 준비합니다.
  • i를 0부터 sz-1까지 반복하며 x[s[i]]를 1씩 늘리고 temp에 s[i]를 추가해 첫 번째 윈도우를 구성합니다.
  • j = 0, i = sz부터 문자열 끝까지 i와 j를 1씩 증가시키며 반복합니다.
    • x의 크기(서로 다른 문자 수)가 maxLetters 이하이면 m[temp]를 1 증가시킵니다.
    • x[temp[0]]을 1 감소시키고, 값이 0이 되면 x에서 해당 키를 삭제합니다.
    • temp의 첫 번째 문자를 제거합니다.
    • x[s[i]]를 1 증가시키고 temp에 s[i]를 추가해 윈도우를 한 칸 밀어냅니다.
  • 반복이 끝난 후에도 x의 크기가 maxLetters 이하이면 마지막 윈도우에 대해 m[temp]를 1 증가시킵니다.
  • ans := 0으로 초기화합니다.
  • 맵 m의 모든 요소를 순회하면서 ans를 각 값과 비교해 최댓값으로 갱신합니다.
  • ans를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n × minSize)이며, 공간 복잡도 역시 저장되는 부분 문자열 개수에 따라 O(n × minSize)입니다.

예제(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