#686

Medium

LeetCode Problem Workspace

Repeated String Match

Find the minimum number of repetitions of string a to make string b a substring of the repeated string a.

Problem Statement

Given two strings a and b, your task is to determine the minimum number of times you should repeat string a so that string b becomes a substring of the repeated string. If it is not possible to make b a substring even after repeating a, return -1.

For example, consider the string a = "abcd" and b = "cdabcdab". Repeating string a three times results in "abcdabcdabcd", where b becomes a substring. If b cannot be made a substring after multiple repetitions, the output should be -1.

Examples

Example 1

Input: a = "abcd", b = "cdabcdab"

Output: 3

We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

Example 2

Input: a = "a", b = "aa"

Output: 2

Example details omitted.

Constraints

1 <= a.length, b.length <= 104
a and b consist of lowercase English letters.

Solution Approach

Initial String Matching

Start by determining the minimum number of repetitions required for the length of a to exceed the length of b. A basic approach is to check if b is already a substring of a.

Repeated String Expansion

To handle edge cases, repeat a enough times so its length surpasses b's length. Then, check if b appears as a substring within the expanded version of a.

Efficient Check and Return

If b is found in the repeated string, return the number of repetitions. If not, return -1. The time complexity is O(M+N), where M is the length of a and N is the length of b.

Complexity Analysis

Metric	Value
Time	O(M+N)
Space	O(1)

The time complexity is O(M+N) due to the string matching operation, where M is the length of string a and N is the length of string b. Space complexity is O(1) as we do not use any additional storage apart from the input strings.

What Interviewers Usually Probe

Ability to handle string manipulations and substring matching efficiently.
Proficiency in optimizing solutions for string-based problems with variable input sizes.
Understanding of complexity trade-offs in terms of time and space for string matching problems.

Common Pitfalls or Variants

Common pitfalls

Not considering edge cases where b might be smaller than a or when it might take multiple repetitions to match.
Misunderstanding the failure condition when it is impossible for b to be a substring of repeated a.
Improper handling of large input sizes, leading to performance inefficiencies.

Follow-up variants

Modify the problem by restricting the maximum number of repetitions.
Allow for case-sensitive string matching to increase complexity.
Test with random large inputs to assess time performance more accurately.

FAQ

What is the time complexity of the Repeated String Match problem?

The time complexity is O(M+N), where M is the length of string a and N is the length of string b.

How do I handle edge cases in Repeated String Match?

Make sure to account for situations where b is smaller than a or cannot be made a substring after multiple repetitions.

Can Repeated String Match be solved without repeating string a?

No, the solution requires repeating string a at least a few times to check if b becomes a substring.

What is the pattern for solving the Repeated String Match problem?

The pattern involves string matching, expanding the repeated string, and checking if b is a substring of the repeated a.

What happens if b cannot be made a substring of repeated a?

If b cannot be a substring after repeating a enough times, the function should return -1.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        m, n = len(a), len(b)
        ans = ceil(n / m)
        t = [a] * ans
        for _ in range(3):
            if b in ''.join(t):
                return ans
            ans += 1
            t.append(a)
        return -1

Continue Practicing

#796 rotate string #459 repeated substring pattern #1023 camelcase matching