Overview

This is a problem where you compare two strings from the beginning and find the maximum length of consecutive matching characters at corresponding positions.

Analysis

This problem can be reduced to comparing the correct PIN \(S\) and Takahashi’s input sequence \(T\) character by character, and finding the “maximum length of a consecutively matching segment.”

Understanding with a Concrete Example

For example, consider the case where \(N = 8\), \(S = \) LLRLRRLL, \(T = \) LLRRRRRL.

Position	1	2	3	4	5	6	7	8
\(S\)	L	L	R	L	R	R	L	L
\(T\)	L	L	R	R	R	R	R	L
Match	✓	✓	✓	✗	✓	✓	✗	✓

The consecutive matching segments are: - Positions 1–3: length 3 - Positions 5–6: length 2 - Position 8: length 1

Therefore, the answer is 3.

Naive Approach

A method that searches for consecutive matching segments from every starting position could take \(O(N^2)\) in the worst case. However, this problem can be solved in a single scan.

Algorithm

We use a method that tracks the length of consecutive segments.

1. Initialize variables current_consecutive (current consecutive match count) and max_consecutive (maximum consecutive match count) to \(0\)
2. Compare the strings character by character from the beginning
   • If \(S[i] = T[i]\), increment current_consecutive by \(1\) and update max_consecutive
   • If \(S[i] \neq T[i]\), the consecutive streak is broken, so reset current_consecutive to \(0\)
3. Output max_consecutive at the end

With this method, the answer can be obtained by scanning the string just once.

Complexity

• Time complexity: \(O(N)\)
  • It runs in linear time since we only scan the string once
• Space complexity: \(O(N)\)
  • \(O(N)\) space is needed to store the input strings \(S\) and \(T\)
  • Only a constant number of additional variables are used

Implementation Notes

• current_consecutive requires only a simple update: increment on each match and reset on a mismatch

• Updating max_consecutive only needs to be done on a match (on a mismatch, current_consecutive becomes \(0\), so the maximum will never be updated)

• In Python, string index access S[i] runs in \(O(1)\), allowing efficient comparison

  Source Code

def solve():
    N = int(input())
    S = input()
    T = input()
    
    max_consecutive = 0
    current_consecutive = 0
    
    for i in range(N):
        if S[i] == T[i]:
            current_consecutive += 1
            max_consecutive = max(max_consecutive, current_consecutive)
        else:
            current_consecutive = 0
    
    print(max_consecutive)

solve()

---

This editorial was generated by claude4.5opus.