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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Repeated String Match

Difficulty: Medium

Problem Description

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b to be a substring of a after repeating it, return -1.

Key Insights

  • The main goal is to determine how many times we need to repeat string a until b becomes a substring.
  • If the length of b is greater than the length of a, we may need to repeat a multiple times.
  • The minimum number of repeats can be estimated based on the lengths of a and b.
  • We should also consider the case where b might start before the complete end of a repeated a.

Space and Time Complexity

Time Complexity: O(n * m) where n is the length of a and m is the length of b.
Space Complexity: O(1) since we are using a constant amount of space.

Solution

To solve this problem, we can follow these steps:

  1. Calculate the minimum number of times a needs to be repeated to cover the length of b.
  2. Construct a repeated version of a based on the calculated number of repeats.
  3. Check if b is a substring of this repeated string. If not, repeat a one more time and check again.
  4. If b is still not found, return -1.

This approach leverages string matching techniques and ensures that we are building the repeated string efficiently.

Code Solutions

def repeatedStringMatch(a: str, b: str) -> int:
    repeat_count = -(-len(b) // len(a))  # Calculate minimum repeats needed
    repeated_a = a * repeat_count
    
    if b in repeated_a:
        return repeat_count
    
    repeated_a += a  # One more repeat to check for overlaps
    if b in repeated_a:
        return repeat_count + 1
    
    return -1
← Back to All Questions