Pythonで「a」から始まる連続増加部分文字列の最長長さを求めるプログラム

問題の概要

小文字の英字と「?」記号を含む文字列 s が与えられます。各「?」については、削除するか、任意の小文字の英字に置き換えることができます。このとき、「a」で始まる連続して増加する部分文字列（例："abcdef" のようにアルファベット順に1文字ずつ進む文字列）の最長の長さを求める必要があります。

例えば、入力が s = "vta???defke" の場合、出力は 6 になります。これは、s を "vtabcdefke" に変換できるためです。変換後の文字列には "abcdef" という連続増加部分文字列が含まれており、これが「a」で始まる最長のものとなります。

解法のアプローチ

この問題は、文字列を一度走査しながら状態を管理することで線形時間 O(n) で解くことができます。基本的な考え方は以下の通りです。

• maxlen：これまでに見つかった最長の長さを記録します。
• length：現在構築中の連続増加列の長さを追跡します。
• qmarks：直前までに出現した「?」の個数を数えます。「?」は任意の文字に置き換えられるため、連続増加列を延ばす「橋渡し」として機能します。

具体的な手順は次の通りです。

• maxlen := 0
• length := 0
• qmarks := 0
• s 内の各文字 c について以下を繰り返します。
  • c が「?」の場合：
    • qmarks := qmarks + 1
  • それ以外の場合：
    • idx := (c のASCIIコード) − ("a" のASCIIコード)
    • length <= idx <= length + qmarks または idx <= qmarks を満たす場合は length := idx + 1、そうでなければ length := 0
    • qmarks := 0
  • maxlen := max(maxlen, min(length + qmarks, 26))
• maxlen を返します。

ポイントの解説

英小文字は26種類しかないため、答えは最大でも26になります。そのため min(length + qmarks, 26) という上限処理が必要です。また、新しい文字 c を処理する際、idx（c のアルファベット上の位置）が現在の length と length + qmarks の範囲内に収まっていれば、「?」を適切な文字に置き換えて連続増加列をつなげられることを意味します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(s):
    maxlen = length = qmarks = 0
    for c in s:
        if c == "?":
            qmarks += 1
        else:
            idx = ord(c) - ord("a")
            length = idx + 1 if length <= idx <= length + qmarks or idx <= qmarks else 0
            qmarks = 0
        maxlen = max(maxlen, min(length + qmarks, 26))
    return maxlen

s = "vta???defke"
print(solve(s))

入力

"vta???defke"

出力

6

まとめ

このアルゴリズムは文字列を1回だけ走査するため、計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。「?」を柔軟なワイルドカードとして扱い、現在の連続増加列の長さとの整合性を逐次チェックすることで、「a」から始まる最長の連続増加部分文字列を正確に求められます。