LeetCode 466: Count The Repetitions

Problem Restatement

We are given two strings and two repetition counts:

s1, n1
s2, n2

The notation [s, n] means string s repeated n times.

For example:

["abc", 3] = "abcabcabc"

Define:

str1 = [s1, n1]
str2 = [s2, n2]

We need to find the maximum integer m such that:

[str2, m]

can be obtained from str1 by deleting some characters.

In other words, we need to count how many full copies of str2 can be formed as a subsequence of str1. The official statement defines [s, n] as repeated concatenation and asks for the maximum m such that [str2, m] can be obtained from str1.

Input and Output

Function shape:

def getMaxRepetitions(s1: str, n1: int, s2: str, n2: int) -> int:
    ...

Examples

Example 1:

s1 = "acb"
n1 = 4
s2 = "ab"
n2 = 2

Then:

str1 = "acbacbacbacb"
str2 = "abab"

From str1, we can form two full copies of "abab" as a subsequence.

Answer:

2

Example 2:

s1 = "abc"
n1 = 1
s2 = "abc"
n2 = 1

Then:

str1 = "abc"
str2 = "abc"

We can form one copy.

Answer:

1

Example 3:

s1 = "abc"
n1 = 4
s2 = "ab"
n2 = 2

Here:

str1 = "abcabcabcabc"
str2 = "abab"

Each two copies of s1 can form one copy of "abab".

So the answer is:

2

First Thought: Build the Full Strings

A direct solution is to build:

full1 = s1 * n1
full2 = s2 * n2

Then repeatedly check how many copies of full2 can be matched as a subsequence of full1.

This is easy to understand, but it fails because n1 and n2 can be as large as 10^6, while each string can have length up to 100.

So the full strings may have length up to:

100 * 1_000_000 = 100_000_000

Building them is wasteful.

Problem With Plain Simulation

We can simulate matching s2 while scanning copies of s1.

For each copy of s1, scan its characters and advance an index in s2.

Whenever we finish one s2, increment a counter.

This avoids building str1, but it can still scan:

len(s1) * n1

characters.

Since len(s1) <= 100 and n1 <= 10^6, this may be acceptable in Python for many cases. But the cleaner solution observes that there are only len(s2) possible positions inside s2.

We can precompute what one copy of s1 does to each possible starting position in s2.

Key Insight

When scanning one full copy of s1, the only state we need is:

index in s2 we are currently trying to match

Suppose this index is j.

After scanning one copy of s1, two things happen:

1. We may complete some number of full s2 matches.
2. We end at some new index in s2.

So for every possible starting index j, precompute:

record[j] = (matched_count, next_index)

where:

Then we apply this transition n1 times.

At the end, we have the number of full s2 copies obtainable from [s1, n1].

Since str2 = [s2, n2], the answer is:

full_s2_matches // n2

Algorithm

First, handle impossible characters.

If s2 contains a character that never appears in s1, then no copy of s2 can be formed.

Return 0.

Then build records.

For every starting index start from 0 to len(s2) - 1:

1. Set j = start.
2. Set count = 0.
3. Scan each character ch in s1.
4. If ch == s2[j], advance j.
5. If j == len(s2), reset j = 0 and increment count.
6. Store (count, j).

Then simulate n1 copies of s1:

matches = 0
j = 0

for _ in range(n1):
    count, j = record[j]
    matches += count

Return:

matches // n2

Walkthrough

Use:

s1 = "acb"
n1 = 4
s2 = "ab"
n2 = 2

Possible starting indices in s2 are:

0  # waiting for 'a'
1  # waiting for 'b'

Start at index 0.

Scan "acb":

a matches s2[0] = a, move to index 1
c does not match s2[1] = b
b matches s2[1] = b, complete one s2

So:

record[0] = (1, 0)

Start at index 1.

Scan "acb":

a does not match s2[1] = b
c does not match s2[1] = b
b matches s2[1] = b, complete one s2

So:

record[1] = (1, 0)

Now apply four copies of s1.

We can form 4 copies of s2 = "ab".

But str2 = [s2, 2] = "abab".

So the final answer is:

4 // 2 = 2

Correctness

For a fixed starting index in s2, scanning one copy of s1 always produces the same result: a fixed number of completed s2 copies and a fixed next index in s2.

The precomputed record table stores exactly this transition for every possible starting index.

The full string [s1, n1] is made of n1 identical copies of s1. Applying the corresponding transition once per copy therefore simulates the same subsequence-matching process as scanning the full repeated string directly.

The variable matches counts how many complete copies of s2 can be obtained from [s1, n1].

Since one copy of str2 consists of n2 copies of s2, the number of complete str2 copies is:

matches // n2

Therefore, the algorithm returns the required maximum repetition count.

Complexity

Let:

a = len(s1)
b = len(s2)

This avoids building either repeated string.

Implementation

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        if n1 == 0:
            return 0

        if not set(s2).issubset(set(s1)):
            return 0

        m = len(s2)
        records = []

        for start in range(m):
            count = 0
            j = start

            for ch in s1:
                if ch == s2[j]:
                    j += 1

                    if j == m:
                        count += 1
                        j = 0

            records.append((count, j))

        matches = 0
        j = 0

        for _ in range(n1):
            count, j = records[j]
            matches += count

        return matches // n2

Code Explanation

First, we handle the case where no copies of s1 exist:

if n1 == 0:
    return 0

Then we check whether every character in s2 appears in s1:

if not set(s2).issubset(set(s1)):
    return 0

If a needed character never appears in s1, no complete s2 can be formed.

The table:

records = []

stores what happens after scanning one s1 from each possible position in s2.

For each starting position:

for start in range(m):

we scan s1 and advance j whenever a character matches:

if ch == s2[j]:
    j += 1

When j == m, one full s2 has been matched:

count += 1
j = 0

After precomputation, we apply the transition once per copy of s1:

for _ in range(n1):
    count, j = records[j]
    matches += count

Finally, divide by n2:

return matches // n2

because the target repeated string contains n2 copies of s2.

Faster Version With Cycle Skipping

The previous version is already efficient enough for the constraints.

We can also detect repeated states during the n1 simulation.

A state is the current index j in s2.

If the same j appears again after some number of s1 copies, then the process has entered a cycle.

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        if n1 == 0:
            return 0

        if not set(s2).issubset(set(s1)):
            return 0

        index = 0
        s1_count = 0
        s2_count = 0
        seen = {}

        while s1_count < n1:
            s1_count += 1

            for ch in s1:
                if ch == s2[index]:
                    index += 1

                    if index == len(s2):
                        s2_count += 1
                        index = 0

            if index in seen:
                prev_s1_count, prev_s2_count = seen[index]

                cycle_s1 = s1_count - prev_s1_count
                cycle_s2 = s2_count - prev_s2_count

                remaining_s1 = n1 - s1_count
                cycles = remaining_s1 // cycle_s1

                s1_count += cycles * cycle_s1
                s2_count += cycles * cycle_s2
            else:
                seen[index] = (s1_count, s2_count)

        return s2_count // n2

The precomputed transition version is simpler and has predictable O(len(s1) * len(s2) + n1) complexity. The cycle-skipping version can be faster when n1 is very large.

Testing

def run_tests():
    s = Solution()

    assert s.getMaxRepetitions("acb", 4, "ab", 2) == 2
    assert s.getMaxRepetitions("abc", 1, "abc", 1) == 1
    assert s.getMaxRepetitions("abc", 4, "ab", 2) == 2
    assert s.getMaxRepetitions("aaa", 3, "aa", 1) == 4
    assert s.getMaxRepetitions("abc", 10, "d", 1) == 0
    assert s.getMaxRepetitions("baba", 11, "baab", 1) == 7
    assert s.getMaxRepetitions("a", 0, "a", 1) == 0

    print("all tests passed")

run_tests()

Test meaning: