【Python】2つの文字列で1文字だけ異なる部分文字列のペアを数える方法

問題概要

2つの文字列 s と t が与えられます。s から空でない部分文字列を1つ選び、その中のちょうど1文字を別の文字に置き換えたとき、結果が t の部分文字列と一致するような組み合わせの総数を求めるのが目的です。

入力例

s = "sts"、t = "tsts"

出力例

6

この場合、s と t から選んだ部分文字列のペアのうち、ちょうど1文字だけ異なるものは次の6組です。

• ("s", "t")：s[0] と t[0]
• ("s", "t")：s[0] と t[2]
• ("t", "s")：s[1] と t[1]
• ("t", "s")：s[1] と t[3]
• ("s", "t")：s[2] と t[0]
• ("s", "t")：s[2] と t[2]

長さ2以上の部分文字列のペアでは1文字違いの組み合わせが存在しないため、合計は6となります。

解法のアプローチ

基本となる考え方は、s の各開始位置と t の各開始位置のすべての組み合わせについて、両者がどこまで一致するかを順番に比較していくというものです。具体的には以下の手順で進めます。

1. n1 := s の長さ、n2 := t の長さとし、答えを格納する変数 ans := 0 で初期化します。
2. s の各インデックス i1 と文字 c1 について、以下を繰り返します。
   • t の各インデックス i2 と文字 c2 について、以下を繰り返します。
     • i := i1、j := i2 とします。
     • i < n1 かつ j < n2 かつ s[i] == t[j] である間、i と j をそれぞれ1ずつ進めます。
     • i < n1 かつ j < n2 かつ s[i] != t[j] である場合（＝1文字だけ異なる位置に到達した場合）：
       • i と j を1ずつ進め、ans を1増やします。
       • その後も s[i] == t[j] が続く限り i と j を進め、一致が続くたびに ans を1増やします。
3. 最後に ans を返します。

ポイントは、「最初に一致しなくなった位置で1回だけ差を許容し、そこから先は完全一致が続く間だけカウントを続ける」という点です。これにより、1文字違いの部分文字列のペアを正確に数えることができます。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(s, t):
    n1 = len(s)
    n2 = len(t)
    ans = 0

    for i1, c1 in enumerate(s):
        for i2, c2 in enumerate(t):
            i = i1
            j = i2

            # 一致している間はポインタを進める
            while i < n1 and j < n2 and s[i] == t[j]:
                i += 1
                j += 1

            # 1文字だけ異なる位置に到達した場合
            if i < n1 and j < n2 and s[i] != t[j]:
                i += 1
                j += 1
                ans += 1
                # 以降も一致が続く限りカウント
                while i < n1 and j < n2 and s[i] == t[j]:
                    i += 1
                    j += 1
                    ans += 1

    return ans

s = "sts"
t = "tsts"
print(solve(s, t))

実行結果

入力

"sts", "tsts"

出力

6

計算量について

開始位置の組み合わせが O(n1 × n2) 通りあり、各ペアの比較に最大 O(min(n1, n2)) かかるため、全体の計算量は O(n1 × n2 × min(n1, n2)) となります。短い文字列であれば十分実用的ですが、長い文字列を扱う場合は動的計画法などを用いた高速化も検討するとよいでしょう。