We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Repeated String Match

Number: 686

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg

Problem Description

Given two strings a and b, determine the minimum number of times a must be repeated such that b becomes a substring of the repeated a. If b can never be a substring, return -1.

Key Insights

  • The key observation is that b will be found within the repeated string a after a sufficient number of repeats, possibly spanning the junction between two copies of a.
  • The initial number of repeats can be approximated by ceiling(|b| / |a|). To handle potential overlaps at the boundaries, one additional repetition might be necessary.
  • A simple check using built-in substring methods is sufficient to verify if b is contained in the repeated string.

Space and Time Complexity

Time Complexity: O(n * k), where n is the length of a and k is the minimum number of repeats (usually a small constant in practice). Space Complexity: O(n * k), which is the space required to construct the repeated string.

Solution

The solution calculates an initial repeat count using the ceiling of the division of b's length by a's length. It then constructs a repeated version of a and checks if b is a substring. Because b could span across the boundary of two adjacent a's, the solution appends one more repetition of a if necessary. If b is still not found, return -1.

Code Solutions

# Function to determine the minimum number of times 'a' must be repeated 
# so that 'b' is a substring of the repeated string.
def repeatedStringMatch(a, b):
    # Calculate the minimum repeats required using ceiling division
    repeat_count = -(-len(b) // len(a))  # This is equivalent to math.ceil(len(b) / len(a))
    # Build the repeated string
    repeated = a * repeat_count
    # Check if b is a substring of the repeated string
    if b in repeated:
        return repeat_count
    # Check with one additional repeat to handle potential overlap between repeats
    if b in (repeated + a):
        return repeat_count + 1
    return -1

# Example usage:
print(repeatedStringMatch("abcd", "cdabcdab"))  # Expected output: 3
← Back to All Questions