Count The Repetitions

Count The Repetitions asks you to count how many times one repeated string fits inside another — but the strings are far too large to ever build. The trick is cycle detection: the process repeats itself, so you find the loop once and multiply past the rest.

The slow way first

The naive plan: build [s1, n1] and [s2, n2] as real strings, then greedily match s2 through s1. But n1 and n2 can be up to 10^6, so [s1, n1] could be tens of millions of characters — building it is too slow and too much memory.

The question to ask: as I scan copy after copy of s1, am I really doing new work each time? No. The only thing that carries between copies is where I am inside s2 — the pointer j. There are only len(s2) possible values of j, so eventually a value of j must repeat. When it does, everything since the last time is a cycle that will keep repeating identically.

The idea: detect the cycle, then multiply

Process s1 one copy at a time. Track matched (how many full s2 strings completed so far) and j (the current index into s2). After finishing each copy, record j → (copies done, matched so far). The first time a j value comes back, the span between the two sightings is a fixed block: a constant number of copies that always produces a constant number of s2 matches. Multiply that block across the remaining copies instead of scanning them.

The key insight: j lives in a tiny range, so the behavior of s1 copies is eventually periodic. Detect the period once, and the rest is arithmetic.

Walk through it

Step through the animation. We scan "acb": "a" matches and advances j, "c" is skipped, "b" completes "ab" and wraps j back to 0. We record j = 0 after copy 1. Scanning copy 2 lands at j = 0 again — a repeat. That is the cycle: 1 copy → 1 match. With n1 = 4 copies that is 4 matched "ab", and dividing by n2 = 2 gives the answer 2.

Pseudocode

matched, j = 0, 0
seen = {0: (0, 0)}                  # j -> (copies done, matched so far)
for each copy k = 1 .. n1:
    for each char c in s1:
        if c == s2[j]:
            j += 1
            if j reached end of s2:
                j = 0
                matched += 1
    if j is new:
        seen[j] = (k, matched)
    else:
        recover (prev_k, prev_m) from seen[j]
        cycle length = k - prev_k copies, cycle gain = matched - prev_m
        jump matched forward across all remaining copies
        stop the loop
return matched // n2

The Python solution

def get_max_repetitions(s1, n1, s2, n2):
    matched, j = 0, 0
    seen = {0: (0, 0)}      # j -> (copies_done, matched)
    for k in range(1, n1 + 1):
        for c in s1:
            if c == s2[j]:
                j += 1
                if j == len(s2):
                    j = 0
                    matched += 1
        if j not in seen:
            seen[j] = (k, matched)
        else:
            prev_k, prev_m = seen[j]
            cycle_k = k - prev_k
            cycle_m = matched - prev_m
            reps = (n1 - prev_k) // cycle_k
            matched = prev_m + reps * cycle_m
            break
    return matched // n2

• matched counts completed copies of s2; j is our position inside s2.
• seen maps each ending j to the (copy number, matched) we had when we last ended a copy there.
• The inner loop is a greedy match: every time s2[j] appears, advance j; when j wraps, one full s2 is done.
• Line 11 stores a brand-new j; the else branch fires when a j repeats — that is the cycle.
• cycle_k copies produce cycle_m matches. reps is how many whole cycles fit in the copies left after prev_k, and we jump matched forward by reps * cycle_m instead of scanning them.
• matched // n2 converts matched s2 strings into copies of [s2, n2].

Complexity

A repeated j must occur within len(s2) + 1 copies (pigeonhole), so the scanning loop runs only that many times no matter how huge n1 is. The seen map holds at most len(s2) entries.

When this pattern shows up

Practice