Overview

Given an \(N\)-digit correct PIN \(S\) and the actually entered button sequence \(T\), the problem asks to find the length of the longest contiguous interval where the characters match.

Analysis

To solve this problem, we need to compare strings \(S\) and \(T\) character by character from the beginning.

For example, consider the case \(S = \text{LRRLR}, T = \text{LRLLR}\): - 1st character: L and L — match (current consecutive count: 1) - 2nd character: R and R — match (current consecutive count: 2) - 3rd character: R and L — mismatch (consecutive streak breaks. Maximum so far: 2) - 4th character: L and L — match (current consecutive count: 1) - 5th character: R and R — match (current consecutive count: 2)

The final answer is \(2\), the maximum among these consecutive matching intervals.

Since the maximum value of \(N\) is \(2 \times 10^5\), an \(O(N)\) algorithm that scans the string once is well within the time limit.

Algorithm

We solve this using Python’s standard library with the following steps:

1. Compare each digit: Using map(operator.eq, s, t), we create a sequence of boolean values (True or False) indicating whether each digit matches.
2. Grouping: Using itertools.groupby, we group consecutive identical values together. This is similar to a “run-length encoding” operation.
3. Extract matching intervals: Among the grouped data, we count the number of elements (length) of each group whose value is True (match).
4. Calculate the maximum: We find the maximum value from the resulting list of lengths. To handle the case where no characters match at all, we set the default value to \(0\).

Complexity

• Time complexity: \(O(N)\)
  • Reading the strings, comparing each character, and scanning with groupby are all linear in \(N\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input strings \(S, T\).

Implementation Notes

• Using itertools.groupby: While it is possible to write the logic for grouping consecutive elements with a loop, using groupby allows for a concise and efficient implementation.

• Handling empty lists: The max() function raises an error when given an empty iterator. To handle the case where Takahashi never pressed the correct button (no matching positions at all), we specify max(..., default=0) to safely output \(0\).

• Fast input: Since \(N\) can be large, we use sys.stdin.read().split() to read all input at once, improving processing speed.

  Source Code

import sys
from itertools import groupby
from operator import eq

def solve():
    # 標準入力からすべてのデータを取得し、空白（改行含む）で分割します。
    # data[0] は N、data[1] は 正しい暗証番号 S、data[2] は 入力されたボタンの列 T となります。
    data = sys.stdin.read().split()
    if len(data) < 3:
        return
    
    s, t = data[1], data[2]
    
    # operator.eq を用いて S と T の各文字を比較し、一致（True）か不一致（False）かのイテレータを作成します。
    # itertools.groupby は連続する同じ値（この場合は True または False）をグループ化します。
    # is_match が True のグループ（正しく入力された連続した区間）の長さを取得します。
    match_lengths = (len(list(group)) for is_match, group in groupby(map(eq, s, t)) if is_match)
    
    # 連続して正しく入力された最大の桁数を出力します。
    # 一度も一致しなかった場合に備えて default=0 を指定します。
    print(max(match_lengths, default=0))

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.