Pythonで文字列の各インデックスから文字cまでの最短距離を求めるリストを作る方法

問題の概要

文字列 s と文字 c が与えられます(c は必ず s 内に存在するものとします)。ここで、s と同じ長さのリストを作成し、その各インデックス i の値を「s[i] から最も近い c までの距離」に設定します。

たとえば、入力が s = "ppqppq"、c = "q" の場合、出力は [2, 1, 0, 1, 1, 0] となります。

出力の内訳

• インデックス 0(p):最寄りの「q」はインデックス 2 → 距離 2
• インデックス 1(p):最寄りの「q」はインデックス 2 → 距離 1
• インデックス 2(q):自身が「q」→ 距離 0
• インデックス 3(p):最寄りの「q」はインデックス 2 → 距離 1
• インデックス 4(p):最寄りの「q」はインデックス 5 → 距離 1
• インデックス 5(q):自身が「q」→ 距離 0

解法の考え方

この問題は、次の手順で解きます。

1. 変数 j に文字列 s の長さを代入します。
2. リスト d を、すべての要素を j - 1(発生しうる最大距離)で初期化して作成します。
3. 変数 x に、s の中で最初に c が出現するインデックスを代入します。
4. i を 0 から j - 1 まで順に処理します。
   • s[i] が c と一致し、かつ i > x の場合は、x を i に更新し、ind を 1 として左側の位置を遡って更新します。d[x - ind] が ind より大きい間だけ値を ind に書き換え、そうでなくなった時点でループを抜けます。
   • その後、d[i] に |x - i|(直近の c までの絶対距離)を代入します。
5. 最後にリスト d を返します。

ポイントは「直前に見つけた c の位置 x」を常に追跡することです。新しい c を発見したタイミングで、それより左側の位置に対して「新しい c の方が近い場合のみ」距離を更新していく仕組みになっています。

Pythonでの実装例

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

def solve(s, c):
    j = len(s)
    d = [j - 1] * j
    x = s.index(c)
    for i in range(j):
        if s[i] == c and i > x:
            x = i
            ind = 1
            while True:
                if d[x - ind] > ind:
                    d[x - ind] = ind
                else:
                    break
                ind += 1
        d[i] = abs(x - i)
    return d

s = "ppqppq"
c = "q"
print(solve(s, c))

入力

"ppqppq", "q"

出力

[2, 1, 0, 1, 1, 0]

より読みやすい別解：左右2回の走査

上記の実装は正しく動作しますが、条件分岐が多くやや複雑です。実務では「左から右」「右から左」の2回の走査で求める方法がシンプルでおすすめです。

def solve(s, c):
    n = len(s)
    INF = float("inf")
    d = [INF] * n

    # 左から右へ走査し、左側の最寄りの c までの距離を記録
    prev = INF
    for i in range(n):
        if s[i] == c:
            prev = i
        d[i] = min(d[i], abs(i - prev))

    # 右から左へ走査し、右側の最寄りの c との距離と比較
    prev = INF
    for i in range(n - 1, -1, -1):
        if s[i] == c:
            prev = i
        d[i] = min(d[i], abs(prev - i))

    return d

print(solve("ppqppq", "q"))  # [2, 1, 0, 1, 1, 0]

どちらの方法も計算量は O(n) ですが、2回の走査を使う方法はロジックの意図が明確になり、バグも生じにくくなります。

まとめ

文字列内の各位置から特定の文字までの最短距離を求める問題は、「直近の出現位置を追跡する」方法でも「両方向からの走査で最小値を取る」方法でも、線形時間 O(n) で解けます。面接や競技プログラミングでも頻出のパターンなので、ぜひマスターしておきましょう。