Rotate the Ring to Match

Medium

You are given two arrays of the same length n: ring and pattern. Position i is a match when ring[i] == pattern[i]. You may rotate ring to the right any number of times: one rotation moves every element from position i to position (i + 1) mod n, so the last element becomes the first. pattern stays as it is. Return the largest number of matching positions you can reach by rotating.

Example 1

ring=[4, 8, 1, 6], pattern=[1, 6, 4, 8] → 4

After two shifts, ring becomes [1, 6, 4, 8] and matches pattern at all four positions.

Example 2

ring=[2, 2, 5], pattern=[5, 3, 2] → 2

One shift gives [5, 2, 2], matching positions 0 and 2. Position 1 can never match, since ring has no 3.

Example 3

ring=[1, 2, 3], pattern=[7, 8, 9] → 0

Constraints

len(ring) = len(pattern)
1 ≤ len(ring) ≤ 3000
1 ≤ ring[i], pattern[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Simulation

Similar problems

Match-Three Cascade Medium Two Gardeners and Their Refills Medium Split Text at the Marks Medium Plus, Minus, Plus Medium Sort Into Three Piles Around a Mark Medium

Input

ring=[4, 8, 1, 6], pattern=[1, 6, 4, 8]

Expected

Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.