C++で条件を満たす部分文字列の最大出現回数を求める方法

問題概要

文字列 s が与えられたとき、次の条件を満たす部分文字列の中で、出現回数が最大となるものの回数を求める問題です。

• 部分文字列に含まれる異なる文字の種類数が maxLetters 以下であること
• 部分文字列の長さが minSize 以上 maxSize 以下であること

たとえば、入力が s = "aababcaab"、maxLetters = 2、minSize = 3、maxSize = 4 の場合、答えは 2 になります。これは、部分文字列 "aab" が元の文字列中に 2 回出現しており、異なる文字が 2 種類（maxLetters 以下）、長さも 3 で指定範囲内という条件を満たしているためです。

解法のアプローチ

この問題は、ハッシュマップとスライディングウィンドウを組み合わせることで効率的に解けます。基本的な手順は以下の通りです。

1. 出現回数を記録するためのマップ m を定義します。
2. サイズ sz を minSize から maxSize の範囲で変えながら、以下を繰り返します。
   • 文字ごとの出現数を管理するマップ x を用意し、一時的な部分文字列 temp を空文字列で初期化します。
   • i を 0 から sz - 1 まで動かし、x[s[i]] を増やしながら temp に文字を追加して、最初のウィンドウを構築します。
   • j = 0、i = sz から開始し、i が文字列の末尾に達するまで両者を 1 ずつ進めます。
     • x のサイズが maxLetters 以下であれば、m[temp] を 1 増やします。
     • x[temp[0]] を 1 減らし、0 になった場合は x からその文字を削除します。
     • temp の先頭の 1 文字を削除します。
     • x[s[i]] を 1 増やし、temp の末尾に s[i] を追加してウィンドウを右へスライドさせます。
   • ループ終了後、最後のウィンドウについても x のサイズが maxLetters 以下であれば m[temp] を 1 増やします。
3. 答え ans を 0 で初期化します。
4. マップ m のすべての要素を走査し、値の最大値を ans に記録します。
5. ans を返します。

なお、サンプルコードでは sz のループを minSize のみに限定しています。これには理由があります。長さ L の部分文字列が k 回出現するなら、それを含むより短い部分文字列も必ず k 回以上出現するため、最小サイズだけを調べれば十分であり、計算量を大幅に削減できるのです。

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

まとめ

この解法では、固定長のスライディングウィンドウですべての候補部分文字列を走査し、ハッシュマップで出現回数を集計しています。計算量は文字列の長さを n とすると O(n × minSize) 程度に抑えられ、大きな入力に対しても効率的に動作します。「短い部分文字列ほど出現回数は多くなる」という性質を利用して探索範囲を絞るのが、このアルゴリズムの重要なポイントです。