Pythonで最小の長さ差となる等しい部分文字列ペアの個数を求める方法

問題の概要

小文字アルファベットのみで構成された2つの文字列が与えられます。このとき、次の条件をすべて満たす四つ組 (p, q, r, s) の個数を求めることを考えます。

• 0 <= p <= q <= 1つ目の文字列の長さ
• 0 <= r <= s <= 2つ目の文字列の長さ
• 1つ目の文字列のインデックス p〜q にある部分文字列と、2つ目の文字列のインデックス r〜s にある部分文字列が完全に一致する
• 上記の条件を満たすすべての四つ組の中で、q − r の値が最小である

たとえば、firstString = 'hgfn'、secondString = 'gfrt' という入力に対する出力は 2 になります。実際、(1, 1, 0, 0) と (2, 2, 1, 1) の2つの四つ組が条件を満たしており、どちらも q − r の値が最小（1）になっています。

アプローチ：各文字の出現位置に注目する

この問題を素朴に全探索すると計算量が膨大になりますが、「最適な四つ組では部分文字列の長さが必ず1文字になる」という性質に着目すれば、非常にシンプルに解けます。

部分文字列をそれ以上伸ばしても、q − r の値が小さくなることはないためです。したがって、両方の文字列に共通して現れる各文字 c について、次の2点だけを考えれば十分です。

• 1つ目の文字列における c の最初の出現位置（インデックス p）
• 2つ目の文字列における c の最後の出現位置（インデックス r）

このとき q = p、s = r として q − r = p − r を計算し、共通するすべての文字の中でこの値が最小となるものを探します。そして、その最小値に一致する文字の個数こそが答えとなります。

アルゴリズムの手順

1. サイズ26の配列 left を無限大で初期化し、1つ目の文字列を走査しながら各文字（a〜z）の最初の出現位置を記録します。
2. サイズ26の配列 right を -1 で初期化し、2つ目の文字列を走査しながら各文字の最後の出現位置を記録します。
3. left[c] が有効な値（無限大以外）である各文字について、left[c] − right[c] を計算し、その最小値 mi を求めます。
4. left[c] と right[c] がどちらも有効で、かつ left[c] − right[c] == mi となる文字の個数を数えます。これが最終的な答えです。

Pythonでの実装例

それでは、上記の手順を実際のコードで確認してみましょう。

def solve(firstString, secondString):
    left = [float('inf')] * 26
    right = [-1] * 26
    res = 0
    mi = float('inf')

    for i, ch in enumerate(firstString):
        left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)

    for i, ch in enumerate(secondString):
        right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)

    for i in range(26):
        if left[i] != float('inf'):
            mi = min(mi, left[i] - right[i])

    for i in range(26):
        if left[i] != float('inf') and right[i] != -1:
            if left[i] - right[i] == mi:
                res += 1

    return res

print(solve('hgfn', 'gfrt'))

実行結果

入力

'hgfn', 'gfrt'

出力

2

計算量の評価

このアルゴリズムの時間計算量は O(n + m)（n、m はそれぞれ2つの文字列の長さ）です。各文字列を一度ずつ走査し、その後にサイズ26の配列を2回確認するだけだからです。また、使用するのはサイズ26の固定配列のみなので、空間計算量は O(1) となります。