C++で最小ウィンドウ部分文字列を求める：スライディングウィンドウ法の解説

問題概要

文字列SとTが与えられたとき、Sの中からTに含まれるすべての文字をカバーする最小のウィンドウ（部分文字列）を見つける問題です。例えば、S = "ABHDAXCVBAGTXATYCB"、T = "ABC" の場合、A・B・Cをすべて含む最短の部分文字列は "CVBA" となるため、これが答えになります。

解法のアプローチ：スライディングウィンドウ

この問題は「スライディングウィンドウ（二つのポインタ）」という手法を使うことで、O(|S| + |T|) の時間計算量で効率的に解くことができます。rightポインタでウィンドウを広げ、条件を満たしたらleftポインタで縮める、という操作を繰り返すのがポイントです。

具体的な手順は以下の通りです。

• Tの各文字の出現回数を記録するマップ m を作成する

• length := Sのサイズ、left := 0、right := 0、ansLeft := 0、ansRight := 0 と初期化する

• counter := Tのサイズ、flag := false、ans := 空文字列 と初期化する

• right が S のサイズ未満である間、以下を繰り返す：

  • c := S[right]
  • c が m に存在する場合：
    　・m[c] > 0 であれば counter を 1 減らす
    　・m[c] を 1 減らす
  • counter == 0 かつ left <= right である間、以下を繰り返す：
    　・right − left + 1 <= length であれば、length := right − left + 1、flag := true、ansLeft := left、ansRight := right と更新する
    　・left == right であればループを抜ける
    　・c := S[left]
    　・c が m に存在する場合は m[c] を 1 増やし、その結果 m[c] > 0 になったら counter を 1 増やす
    　・left を 1 増やす
  • right を 1 増やす

• flag が false のままなら空文字列を返す（条件を満たすウィンドウが存在しないことを意味する）

• それ以外の場合は、S[ansLeft] から S[ansRight] までの文字を連結したものを ans として返す

アルゴリズムのポイント

rightポインタを進めてウィンドウを右へ拡張し、Tに必要な文字がすべて揃った状態（counter == 0）になった時点で、leftポインタを進めて不要な文字を取り除きながらウィンドウを縮小していきます。こうすることで、条件を満たす中で最も短いウィンドウを無駄なく探索できます。

C++実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string minWindow(string s, string x) {
        map <char, int> m;
        for(int i =0;i<x.size();i++)m[x[i]]++;
        int length = s.size();
        int left = 0, right = 0 , ansLeft = 0, ansRight = 0;
        int counter = x.size();
        bool flag = false;
        string ans = "";
        while(right<s.size()){
            char c = s[right];
            if(m.find(c)!=m.end()){
                if(m[c]>0)counter--;
                m[c]--;
            }
            while(counter == 0 && left<=right){
                if(right-left+1 <=length){
                    length = right-left+1;
                    flag = true;
                    ansLeft = left;
                    ansRight = right;
                }
                if(left == right)break;
                c = s[left];
                if(m.find(c)!=m.end()){
                    m[c]++;
                    if(m[c]>0)counter++;
                }
                left++;
            }
            right++;
        }
        if(!flag)return ans;
        else
        for(int i =ansLeft;i<=ansRight;i++)ans+=s[i];
        return ans;
    }
};
main(){
    Solution ob;
    cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
}

入力

"ABHDAXCVBAGTXATYCB"
"ABC"

出力

CVBA

計算量

leftとrightの各ポインタは、それぞれ最大でも文字列Sの長さ分しか移動しないため、時間計算量は O(|S| + |T|) となります。また、マップにはTに含まれる文字種のみを格納するため、空間計算量は O(|T|)（実際には使用されるユニークな文字数に依存）です。全探索のようにSのすべての部分文字列を調べる方法（O(n²)以上）と比べても、非常に効率的な解法といえます。