概要

正しい暗証番号 \(S\) と実際の入力 \(T\) を比較し、連続して一致した（間違えずに押せた）最大の長さを求めます。

考察

各桁 \(i\) について、\(S[i]\) と \(T[i]\) が一致していれば「正しい」、一致していなければ「間違い」です。求めたいのは「正しい」が連続する区間の最大長、つまり 一致する位置が連続する最長区間の長さです。

素朴に「一致が続く限りカウントし、間違えたらリセット」をしても \(O(N)\) で解けますが、この解法を別視点で捉えると、

• 「間違えた位置（不一致の位置）」が区切りになっている
• 不一致の位置と次の不一致の位置の間にある一致の個数が、連続正解の長さ

と分かります。

例えば、\(N=8\) で不一致が位置 \(2,5\)（0-index）にあるとすると、
不一致リストに両端として \(-1\) と \(N\) を加えて [-1, 2, 5, 8] とでき、 - \((-1, 2)\) の間の一致数は \(2 - (-1) - 1 = 2\) - \((2, 5)\) の間は \(5 - 2 - 1 = 2\) - \((5, 8)\) の間は \(8 - 5 - 1 = 2\)

最大は 2 となります。
この「不一致位置を並べて、隙間の最大」を取る方法は実装が簡潔でミスしにくいのが利点です。

アルゴリズム

1. \(S\) と \(T\) を左から見ていき、不一致の位置 \(i\)（\(S[i] \neq T[i]\)）を配列 mismatches に入れる。
2. 連続区間の端を扱いやすくするため、先頭に \(-1\)、末尾に \(N\) を追加する。
   • mismatches = [-1, (不一致の位置...), N]
3. mismatches の隣り合う要素 prev, nxt ごとに、その間の一致連続長は \(nxt - prev - 1\)。
4. その最大値を答えとして出力する。

計算量

• 時間計算量: \(O(N)\)（1回走査して最大を取るだけ）
• 空間計算量: \(O(K)\)（不一致の個数を \(K\) とすると mismatches に \(K+2\) 個保存）

実装のポイント

• 両端に \(-1\) と \(N\) を入れることで、先頭・末尾の連続一致区間も同じ式 \(nxt - prev - 1\) で処理できます（場合分け不要）。

• 入力サイズが大きいので、sys.stdin.read() を使って高速に読み取っています。

  ソースコード

import sys

def solve():
    it = iter(sys.stdin.read().split())
    N = int(next(it))
    S = next(it).strip()
    T = next(it).strip()

    mismatches = [-1]
    mismatches.extend(i for i, (a, b) in enumerate(zip(S, T)) if a != b)
    mismatches.append(N)

    ans = 0
    for prev, nxt in zip(mismatches, mismatches[1:]):
        ans = max(ans, nxt - prev - 1)

    print(ans)

if __name__ == "__main__":
    solve()

この解説は gpt-5.2-high によって生成されました。