Overview

Compare the correct PIN with Takahashi’s input, and find the maximum number of consecutive digits that were entered correctly.

Analysis

In this problem, we need to compare two strings \(S\) (the correct PIN) and \(T\) (the entered button sequence), and find the maximum length of a “consecutive matching subsequence.”

For example, consider the following input:

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

The match/mismatch at each digit is as follows:

In this example, the first 4 digits match consecutively, which is the maximum consecutive match length.

A naive approach would be to check matches for all substrings, but this has a time complexity of \(O(N^2)\), which cannot be processed in time under the constraint \(N \leq 2 \times 10^5\).

Instead, we use a linear scan approach that maintains the “current consecutive match length” while updating the maximum value. This allows us to obtain the answer in a single pass.

Algorithm

1. Compare strings \(S\) and \(T\), and create a list match containing flags (1 or 0) indicating whether each digit matches.
2. Find the maximum length of consecutive 1s in this list:
   • Maintain the current consecutive length current_len and the maximum length so far max_len.
   • Scan the list from the beginning; if the value is 1, increment current_len and update max_len.
   • If a 0 appears, reset current_len to 0.
3. Output the final max_len.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• By preprocessing the match at each digit into a match list, the logic becomes simpler.

• In the consecutive length update process, make sure not to forget to reset current_len in the else branch.

  Source Code

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()

This editorial was generated by qwen3-coder-480b.