Jobs

Interviews

Discussions

Repeated Substring Pattern

Easy

Google

3 views

Topics:

Strings

Given a string s, determine if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

For example:

If s = "abab", return true because it is the substring "ab" repeated twice.
If s = "aba", return false.
If s = "abcabcabcabc", return true because it is the substring "abc" repeated four times or the substring "abcabc" repeated twice.

Consider the following constraints:

1 <= s.length <= 10^4
s consists of lowercase English letters.

Repeated Substring Pattern

Easy

Google

3 views

Topics:

Strings

Given a string s, determine if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

For example:

If s = "abab", return true because it is the substring "ab" repeated twice.
If s = "aba", return false.
If s = "abcabcabcabc", return true because it is the substring "abc" repeated four times or the substring "abcabc" repeated twice.

Consider the following constraints:

1 <= s.length <= 10^4
s consists of lowercase English letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string be empty or null? What should I return in those cases?
Are there any constraints on the length of the input string?
By 'repeated substring pattern', do you mean the entire string is formed by repeating the substring one or more times?
If multiple substrings can form the pattern, is any valid substring acceptable, or is there a preference (e.g., shortest, longest)?
Is the input string guaranteed to be ASCII or should I expect unicode characters?

Brute Force Solution

Approach

The brute force method for finding a repeating substring pattern is like trying every possible piece of the original string and seeing if that piece can be repeated to make the whole thing. We systematically check smaller and smaller chunks to see if they form the core repeating unit.

Here's how the algorithm would work step-by-step:

First, consider the possibility that the entire string is the repeating unit. Obviously, that won't repeat unless the string is empty, but we need to start somewhere.
Next, consider that the first half of the string is the repeating unit. See if repeating that first half gives you the entire original string.
Then, consider that the first third of the string is the repeating unit. Check if repeating that first third gives you the entire original string.
Continue this process, each time checking shorter and shorter starting sections, making sure you can actually repeat it to make the entire string.
For each of these potential repeating units, check if repeatedly concatenating it creates the original string.
If at any point you find a repeating substring that makes the original string, you're done! It means the original string is formed by repeating the shorter substring.

Code Implementation

def repeated_substring_pattern(input_string):
    string_length = len(input_string)

    # Iterate through possible substring lengths
    for substring_length in range(1, string_length):

        #Check if substring length is a divisor
        if string_length % substring_length == 0:

            number_of_repeats = string_length // substring_length
            substring = input_string[:substring_length]

            # Build the repeated string
            repeated_string = substring * number_of_repeats

            # Compare repeated string to the input
            if repeated_string == input_string:
                return True

    # No repeating substring found
    return False

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through possible substring lengths, from n down to 1, which can be considered O(n). The inner loop, inside each iteration of the outer loop, constructs a repeated string and compares it to the original string, which takes O(n) time in the worst case. Therefore, the overall time complexity is approximately O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The algorithm iterates through possible substring lengths and constructs repeated strings for comparison. However, it does not use any auxiliary data structures that scale with the input string's size N. The substring and repeated string creations within the loop are likely optimized by the underlying language to avoid significant extra space allocation, or are overwritten. Therefore, the space used remains constant regardless of the input size N, resulting in O(1) space complexity.

Optimal Solution

Approach

The core idea is to see if a given string is built by repeating a smaller string multiple times. We'll cleverly use string manipulation to figure out if this repetition exists, avoiding lots of unnecessary checks.

Here's how the algorithm would work step-by-step:

First, double the original string.
Then, remove the very first and very last characters of this doubled string.
Now, check if the original string exists inside this modified, doubled string.
If the original string is found within the modified doubled string, it means the original string is formed by repeating a smaller substring. If not found, it is not a repeated substring pattern.

Code Implementation

def repeated_substring_pattern(input_string):
    doubled_string = input_string + input_string

    modified_string = doubled_string[1:-1]

    # Removing the first and last characters is crucial
    # to avoid trivial matches of the original string

    if input_string in modified_string:
        # If the original string is found, it's a repeated pattern
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n) – Doubling the string takes O(n) time, where n is the length of the original string. Removing the first and last characters also takes O(1) time (constant). The dominant operation is checking if the original string is a substring of the modified doubled string, which can be implemented using algorithms like KMP with O(n) time complexity. Therefore, the overall time complexity is O(n).

Space Complexity

O(N) – The dominant space usage comes from creating a doubled string of length 2N in step 1. Then, the modification in step 2 creates a string of length 2N-2, which is still linearly dependent on the input string's length, N. The 'find' operation in step 3 itself doesn't allocate significant extra space. Therefore, the auxiliary space is primarily determined by the doubled string's size, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or Empty String	Return false immediately, as an empty string cannot have a repeated substring pattern.
String of length 1	Return false, a single-character string cannot have a repeating substring.
String with all identical characters	The solution should correctly identify a single character repeated as a valid repeating substring pattern (e.g. 'aaaa').
String equal to a single repeating character like 'a'	The code should return false if the string has only one distinct character and is not made of repeating substrings larger than 1 character
Very long strings exceeding memory constraints	Ensure the solution uses space-efficient techniques, perhaps limiting substring generation or checking length divisors efficiently.
String composed of a repeating substring exactly twice	Solution should return true if the first half equals the second half.
String composed of non-repeating characters (e.g., 'abcdefg')	The algorithm should return false, as no repeating substring pattern exists.
String where the substring repeats more than twice	Verify the solution correctly identifies patterns where the substring repeats multiple times (e.g., 'ababab').

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string be empty or null? What should I return in those cases?
Are there any constraints on the length of the input string?
By 'repeated substring pattern', do you mean the entire string is formed by repeating the substring one or more times?
If multiple substrings can form the pattern, is any valid substring acceptable, or is there a preference (e.g., shortest, longest)?
Is the input string guaranteed to be ASCII or should I expect unicode characters?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider the possibility that the entire string is the repeating unit. Obviously, that won't repeat unless the string is empty, but we need to start somewhere.
Next, consider that the first half of the string is the repeating unit. See if repeating that first half gives you the entire original string.
Then, consider that the first third of the string is the repeating unit. Check if repeating that first third gives you the entire original string.
Continue this process, each time checking shorter and shorter starting sections, making sure you can actually repeat it to make the entire string.
For each of these potential repeating units, check if repeatedly concatenating it creates the original string.
If at any point you find a repeating substring that makes the original string, you're done! It means the original string is formed by repeating the shorter substring.

Code Implementation

def repeated_substring_pattern(input_string):
    string_length = len(input_string)

    # Iterate through possible substring lengths
    for substring_length in range(1, string_length):

        #Check if substring length is a divisor
        if string_length % substring_length == 0:

            number_of_repeats = string_length // substring_length
            substring = input_string[:substring_length]

            # Build the repeated string
            repeated_string = substring * number_of_repeats

            # Compare repeated string to the input
            if repeated_string == input_string:
                return True

    # No repeating substring found
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, double the original string.
Then, remove the very first and very last characters of this doubled string.
Now, check if the original string exists inside this modified, doubled string.
If the original string is found within the modified doubled string, it means the original string is formed by repeating a smaller substring. If not found, it is not a repeated substring pattern.

Code Implementation

def repeated_substring_pattern(input_string):
    doubled_string = input_string + input_string

    modified_string = doubled_string[1:-1]

    # Removing the first and last characters is crucial
    # to avoid trivial matches of the original string

    if input_string in modified_string:
        # If the original string is found, it's a repeated pattern
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty String	Return false immediately, as an empty string cannot have a repeated substring pattern.
String of length 1	Return false, a single-character string cannot have a repeating substring.
String with all identical characters	The solution should correctly identify a single character repeated as a valid repeating substring pattern (e.g. 'aaaa').
String equal to a single repeating character like 'a'	The code should return false if the string has only one distinct character and is not made of repeating substrings larger than 1 character
Very long strings exceeding memory constraints	Ensure the solution uses space-efficient techniques, perhaps limiting substring generation or checking length divisors efficiently.
String composed of a repeating substring exactly twice	Solution should return true if the first half equals the second half.
String composed of non-repeating characters (e.g., 'abcdefg')	The algorithm should return false, as no repeating substring pattern exists.
String where the substring repeats more than twice	Verify the solution correctly identifies patterns where the substring repeats multiple times (e.g., 'ababab').