概要

正しい暗証番号と高橋君の入力を比較し、連続して正しく入力できた最大の桁数を求めます。

考察

この問題では、2つの文字列 \(S\)（正しい暗証番号）と \(T\)（入力したボタン列）を比較し、「一致している連続する部分列」の最大長を求める必要があります。

例えば、以下のような入力を考えます：

N = 5
S = "LRLRR"
T = "LRLRL"

このとき、各桁の一致・不一致は次のようになります：

この例では最初の4桁が連続して一致しており、これが最大の連続一致長となります。

素朴な方法として、すべての部分列について一致を確認する方法がありますが、その計算量は \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) では時間内に処理できません。

そこで、線形探索で「現在の連続一致長」を保持しながら、最大値を更新していく方法を使います。これにより、一度の走査で答えを得ることができます。

アルゴリズム

1. 文字列 \(S\) と \(T\) を比較し、各桁が一致しているかどうかのフラグ（1 or 0）を持つリスト match を作成します。
2. このリストに対して、連続する1の最大長を求める処理を行います：
   • 現在の連続長 current_len と、これまでの最大長 max_len を管理します。
   • リストを前から見ていき、1なら current_len を増やし、max_len を更新します。
   • 0が現れたら、current_len を0に戻します。
3. 最終的な max_len を出力します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 各桁の一致を前処理で match リストとして持つことで、ロジックがシンプルになります。

• 連続長の更新処理では、else で current_len をリセットすることを忘れないようにしましょう。

  ソースコード

def solve():
    N = int(input())
    S = input().strip()
    T = input().strip()

    # 一致する場所を1、異なる場所を0としたリストを作成
    match = [1 if S[i] == T[i] else 0 for i in range(N)]

    # 連続する1の最大長を求める
    max_len = 0
    current_len = 0

    for val in match:
        if val == 1:
            current_len += 1
            max_len = max(max_len, current_len)
        else:
            current_len = 0

    print(max_len)

if __name__ == "__main__":
    solve()

この解説は qwen3-coder-480b によって生成されました。