Pythonで連続する同じ文字を避けながら「?」を置き換えるプログラムの実装方法

問題の概要

小文字のアルファベットと「?」のみで構成された文字列 s が与えられたとします。ここで、すべての「?」を小文字のアルファベットに置き換え、最終的な文字列の中に同じ文字が連続して現れないようにする必要があります。条件を満たす答えが複数存在する場合は、そのうちのどれか1つを返せば構いません。

例えば、入力が s = "hel??" の場合、出力は helab になります。1つ目の「?」には「l」以外の任意の文字を割り当てることができ、1つ目が確定した後は、2つ目の「?」には直前の文字（この場合は「a」）以外の任意の文字を割り当てます。

解法の考え方

この問題は、文字列を先頭から順に走査し、「?」を見つけるたびに両隣の文字と重複しないアルファベットを選んで埋めていくことで解決できます。具体的な手順は以下の通りです。

• 文字列の長さが1の場合：

  • s が「?」であれば「a」を返す
  • それ以外は s をそのまま返す

• 文字列 s を文字のリストに変換する

• i を 0 から s の長さ - 1 まで繰り返す：

  • s[i] が「?」の場合、以下の優先順位で文字を決定する：

    • i が先頭（0）で、次の文字も「?」なら → 「a」を代入
    • i が先頭で、次の文字が「a」なら → 「b」を代入
    • i が先頭なら → 「a」を代入
    • i が末尾で、前の文字が「a」なら → 「b」を代入
    • i が末尾なら → 「a」を代入
    • 前の文字が「a」で、次の文字が「?」なら → 「b」を代入
    • 次の文字が「?」なら → 「a」を代入
    • （前が「a」・次が「b」）または（前が「b」・次が「a」）なら → 「c」を代入
    • 前後のいずれかに「a」があるなら → 「b」を代入
    • 上記のいずれにも該当しない場合 → 「a」を代入

• リスト内の文字を結合して文字列として返す

このアルゴリズムの計算量は O(n) であり、文字列を一度走査するだけで答えが求まるため、非常に効率的な手法です。

Pythonでの実装例

以下の実装例を見ると、処理の流れがより理解しやすくなります。

def solve(s):
    if len(s) == 1 :
        if s == "?":
            return "a"
        return s
    s = list(s)
    for i in range(len(s)):
        if s[i] == "?":
            if i == 0 and s[i+1] == "?":
                s[i] = "a"
            elif i == 0 and s[i+1] == "a":
                s[i] = "b"
            elif i == 0:
                s[i] = "a"
            elif i == len(s)-1 and s[i-1] == "a":
                s[i] = "b"
            elif i == len(s)-1:
                s[i] = "a"
            elif s[i-1] == "a" and s[i+1] == "?":
                s[i] = "b"
            elif s[i+1] == "?":
                s[i] = "a"
            elif (s[i-1] == "a" and s[i+1] == "b") or (s[i-1] == "b" and s[i+1] == "a"):
                s[i] = "c"
            elif "a" in (s[i-1],s[i+1]):
                s[i] = "b"
            else:
                s[i] = "a"
    return "".join(s)

s = "hel??"
print(solve(s))

入力

"hel??"

出力

helab