Pythonで指定した制約条件下で文字列Aから文字列Bを作成できるか判定する方法

問題の概要

2つの文字列 s・t と、2つの整数 p・q が与えられます。このとき、次の条件をすべて満たして文字列 t を文字列 s から作り出せるかどうかを判定するのが本記事のテーマです。

• 文字列 s を先頭から p 文字ずつのグループに分割する(最後のグループのみ p 文字以下でもよい)
• 各グループから取り出せる文字は最大 q 個まで
• t に含まれる文字の並び順は、s 内での出現順序と一致していること

例として、s = "mnonnopeqrst"、t = "moprst"、p = 5、q = 2 という入力を考えてみます。この場合、答えは True になります。s は「mnonn」「opeqr」「st」の3つのグループに分割でき、1つ目と2つ目のグループからそれぞれ2文字の部分文字列「mo」と「pr」を取り出し、3つ目のグループには「st」がそのまま含まれているため、これらを連結すれば t が完成するからです。

解法の考え方

この問題は、貪欲法(グリーディー法)と二分探索を組み合わせることで効率的に解けます。大まかな手順は以下の通りです。

1. temp := キーごとに空のリストを持つ辞書を用意し、s の各文字について出現位置(インデックス)をすべて登録する
2. l := s と同じ長さのリストを 0 で初期化する(各グループから使用した文字数のカウンター)
3. 探索開始位置 low を 0 に設定する
4. t の各文字について以下を繰り返す:
   • その文字が出現するインデックスのリスト indices を取得する
   • bisect_left で indices の中から low 以上となる最小インデックスの位置 it を求める
   • it が indices のサイズと一致する場合、必要な文字がもう残っていないので False を返す
   • count := indices[it] // p で、その文字が属するグループ番号を求める
   • l[count] を 1 増やし、l[count] が q 以上になったら次のグループへ移行(low := (count + 1) × p)。そうでなければ low := indices[it] + 1 として同じグループ内で探索を続ける
5. すべての文字を処理できたら True を返す

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

from bisect import bisect_left
from collections import defaultdict

def solve(s, t, p, q):
    # 各文字の出現位置を記録する辞書
    temp = defaultdict(list)
    # 各グループから使用した文字数のカウンター
    l = [0] * len(s)

    for i in range(len(s)):
        temp[s[i]].append(i)

    low = 0
    for ch in t:
        indices = temp[ch]
        it = bisect_left(indices, low)
        if it == len(indices):
            return False
        count = indices[it] // p
        l[count] += 1
        if l[count] >= q:
            # このグループを使い切ったので次のグループへ
            count += 1
            low = count * p
        else:
            low = indices[it] + 1
    return True

s = "mnonnopeqrst"
t = "moprst"
p = 5
q = 2
print(solve(s, t, p, q))

入力

"mnonnopeqrst", "moprst", 5, 2

出力

True

処理の流れを追う

上記の例では、次のように処理が進みます。

• 'm'(インデックス0)をグループ0から取得 → 残り1個
• 'o'(インデックス2)をグループ0から取得 → グループ0を使い切ったので、次はグループ1から探索
• 'p'(インデックス6)と 'r'(インデックス9)をグループ1から取得 → グループ1も使い切り
• 's'(インデックス10)と 't'(インデックス11)をグループ2から取得

このように、各グループからちょうど q 文字ずつ取り出す形で t が構成できるため、結果は True となります。

計算量について

このアルゴリズムでは、文字ごとの出現位置リストが常にソート済みであることを利用し、bisect_left(二分探索)によって次の候補位置を O(log n) で見つけられます。そのため、前処理の O(|s|) と探索の O(|t| log |s|) を合わせても計算量は非常に小さく、長い文字列に対しても高速に動作します。