【C++】最小ウィンドウ部分列（Minimum Window Subsequence）の求め方

2つの文字列 S と T が与えられたとき、「T が部分列（サブシーケンス）として含まれる」ような S の最短の部分文字列 W を求める問題を考えてみましょう。S の中に T のすべての文字をカバーできるウィンドウが存在しない場合は空文字列を返し、条件を満たすウィンドウが複数ある場合は、開始位置が最も左側にあるものを返します。

たとえば、入力が S = "abcdebdde"、T = "bde" の場合、出力は "bcde" になります。これは "bdde" よりも先に出現するためです。また、"deb" が答えにならないのは、ウィンドウ内で T の文字が必ず順序どおりに現れる必要があるからです。

アルゴリズムの考え方

この問題は、前方向へのスキャンと後方向への巻き戻しを組み合わせた2ポインタ法で効率よく解くことができます。具体的な手順は以下のとおりです。

1. 変数を初期化します。tidx := 0、tlen := T のサイズ、n := S のサイズ、i := 0、length := 無限大、start := -1。
2. i < n の間、以下の処理を繰り返します。
   • S[i] が T[tidx] と一致したら、tidx を1増やします。
   • tidx が tlen と等しくなったら、T 全体のマッチが完了したことを意味します。
     • end := i + 1 としてウィンドウの終端を記録します。
     • tidx を1減らし、i を減らしながら逆方向へ走査します。S[i] が T[tidx] と一致するたびに tidx を減らすことで、ウィンドウの左端（開始位置）を特定します。
     • i を1増やしてウィンドウの開始位置に合わせ、tidx も1増やして 0 に復元します。
     • end - i が現在の length より小さければ、length := end - i、start := i として最短ウィンドウを更新します。
   • i を1増やして次の文字へ進みます。

ループ終了後、start が -1 以外であれば、S[start] から S[start + length - 1] までの文字をつなぎ合わせて結果文字列 ret を構築し、それを返します。start が -1 のままなら、該当するウィンドウが存在しないため空文字列が返されます。

計算量について

T 全体のマッチが完了するたびに後方へ巻き戻す処理が発生するため、最悪計算量は O(|S| × |T|) となります。ただし、多くのケースでは非常に高速に動作します。補助配列を使用しないため、結果文字列を除く空間計算量は O(1) です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string minWindow(string S, string T) {
        int tidx = 0;
        int tlen = T.size();
        int n = S.size();
        int i = 0;
        int length = INT_MAX;
        int start = -1;
        string ret;
        while (i < n) {
            if (S[i] == T[tidx]) {
                tidx++;
                if (tidx == tlen) {
                    int end = i + 1;
                    tidx--;
                    while (tidx >= 0) {
                        if (S[i] == T[tidx]) {
                            tidx--;
                        }
                        i--;
                    }
                    i++;
                    tidx++;
                    if (end - i < length) {
                        length = end - i;
                        start = i;
                    }
                }
            }
            i++;
        }
        if (start != -1)
        for (int i = start; i < start + length; i++)
        ret += S[i];
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.minWindow("abcdebdde", "bde"));
}

入力

"abcdebdde", "bde"

出力

"bcde"