Pythonで2つの同一文字の間に挟まれた最長部分文字列を求めるプログラム

文字列 s が与えられたとき、同じ文字2つに挟まれた部分文字列のうち、両端の2文字を除いた部分の最大の長さを求める問題を考えます。該当する部分文字列が存在しない場合は、-1 を返します。

例えば、s = "level" の場合、出力は 3 になります。これは、先頭と末尾の "l" の間に "eve"(長さ3)が挟まれているためです。

解法のアプローチ

この問題は、各文字の出現位置を記録し、同じ文字の最初の出現位置と最後の出現位置の差を調べることで効率的に解けます。手順は以下の通りです。

• memo := 新しいマップ(辞書)を作成する
• i を 0 から s のサイズ - 1 まで繰り返す:
  • s[i] が memo に存在する場合は、memo[s[i]] の末尾に i を追加する
  • 存在しない場合は、memo[s[i]] := 要素 i のみを持つリストを作成する
• best := 0 で初期化する
• memo の各キーについて、best := max(best, memo[key] の最後の要素 − memo[key] の最初の要素) を計算する
• best - 1 を返す

Pythonでの実装例

def solve(s):
    memo = {}
    for i in range(len(s)):
        if s[i] in memo:
            memo[s[i]].append(i)
        else:
            memo[s[i]] = [i]

    best = 0
    for key in memo:
        best = max(best, memo[key][-1] - memo[key][0])
    return best - 1

s = "level"
print(solve(s))

入力

"level"

出力

3

アルゴリズムのポイント

このアルゴリズムの計算量は、時間・空間ともに O(n)(n は文字列の長さ)です。同じ文字の間隔が最大になるのは必ず最初の出現位置と最後の出現位置の組み合わせであるため、それぞれの文字についてこの2点だけを比較すれば十分です。

また、すべての文字が1回しか出現しない場合、best は 0 のままになるため、best - 1 = -1 が返されます。これにより、「該当する部分文字列が存在しない場合は -1 を返す」という条件も正しく処理されます。