Pythonで重複しない部分文字列の最大数を求めるプログラム

問題概要

小文字の英字のみで構成された文字列 s が与えられたとき、次の2つの条件を満たす「空でない部分文字列」の最大個数を求めます。

• 選んだ部分文字列同士は互いに重ならない(オーバーラップしない)
• ある部分文字列が特定の文字 ch を含むなら、その文字 ch の出現箇所をすべて含まなければならない

さらに、条件を満たす解が複数存在して部分文字列の個数が同じ場合は、合計長が最小になる解を返します。

入力例と出力例

たとえば、入力が s = "pqstpqqprrr" の場合、出力は ["s", "t", "rrr"] となります。条件を満たす候補としては "pqstpqqprrr"、"pqstpqqp"、"st"、"s"、"t"、"rrr" があり、この中で個数が最大(3個)かつ合計長が最小となる組み合わせが ["s", "t", "rrr"] だからです。

解法のアプローチ

この問題は、各文字について「最初に出現する位置」と「最後に出現する位置」を活用することで効率的に解くことができます。手順は以下の通りです。

1. right: 文字列 s に含まれる各文字について、最も右側(末尾側)の出現位置を求め、昇順にソートしたリストを作成します。
2. left: right に格納された各インデックス i に対応する文字 s[i] について、最も左側(先頭側)の出現位置を求めたリストを作成します。
3. has(空リスト)と gen(空リスト)を用意します。
4. i を 0 から right のサイズ - 1 まで繰り返します。
   • gen の末尾に、文字 s[right[i]] だけを要素とする集合を追加します。
   • has の末尾に、「区間 [left[i]+1, right[i]-1] に含まれる文字の集合」から「gen の末尾の要素」を差し引いた集合を追加します。
   • j を has のサイズ - 2 から 0 まで減少させながら、次の判定を行います。
     • (has の末尾の要素 AND gen[j]) かつ (has[j] AND gen の末尾の要素) が空でない場合:
       • gen の末尾 := gen の末尾 OR gen[j]
       • has の末尾 := (has の末尾 OR has[j]) − gen の末尾
       • has[j] と gen[j] を削除します。
5. res(新しいリスト)と p_right = -1 を用意します。
6. ind を 0 から has のサイズ - 1 まで繰り返します。
   • l := 「s[i] が gen[ind] に含まれるような left の要素 i」の最小値
   • r := 「s[i] が gen[ind] に含まれるような right の要素 i」の最大値
   • p_right < l である場合:
     • res の末尾に s[l から r までの部分文字列] を追加します。
     • p_right := r と更新します。
7. res を返します。

実装例

それでは、実際のPythonコードを見て理解を深めましょう。

def solve(s):
    right = sorted([s.rindex(ch) for ch in set(s)])
    left = [s.index(s[i]) for i in right]

    has, gen = [], []
    for i in range(len(right)):
        gen.append(set(s[right[i]]))
        has.append(set(s[left[i] + 1:right[i]]) - gen[-1])

    for j in range(len(has) - 2, -1, -1):
        if (has[-1] & gen[j]) and (has[j] & gen[-1]):
            gen[-1] = gen[-1] | gen[j]
            has[-1] = (has[-1] | has[j]) - gen[-1]
            del has[j], gen[j]

    res, p_right = [], -1
    for ind in range(len(has)):
        l = min([i for i in left if s[i] in gen[ind]])
        r = max([i for i in right if s[i] in gen[ind]])
        if p_right < l:
            res.append(s[l : r + 1])
            p_right = r

    return res

s = "pqstpqqprrr"
print(solve(s))

入力

"pqstpqqprrr"

出力

['s', 't', 'rrr']