Repeated Substring Pattern - Leetcode Solution

The problem statement for the Repeated Substring Pattern problem on LeetCode is as follows:

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

To solve this problem, we need to check if the given string s can be constructed by taking a substring of it and appending multiple copies of the substring together. If this is true, we need to return true, otherwise, we need to return false.

One approach to solve this problem is to find all possible substrings of the given string s and then check if any of these substrings can be used to construct the given string s by appending multiple copies of the substring together.

To find all the possible substrings of the given string s, we can use a loop to find all possible substrings starting from the first character of the string. For each starting index, we can use another loop to find all possible substrings starting from that index. We can keep track of all the substrings we find in a set to avoid duplicate substrings.

Once we have found all the possible substrings of the given string s, we can iterate over each substring and check if it can be used to construct the given string s by appending multiple copies of the substring together. We can do this by first calculating the length of the substring and then checking if the length of the given string s is a multiple of the length of the substring. If this is true, we can check if the given string s can be constructed by appending multiple copies of the substring together. If this is true, we can return true, otherwise, we continue iterating over the remaining substrings.

If we have iterated over all the possible substrings and none of them can be used to construct the given string s by appending multiple copies of the substring together, we can return false.

Here is the Python code to implement the above approach:

def repeatedSubstringPattern(s: str) -> bool:
    substrings = set()
    n = len(s)
    
    # Find all possible substrings of the given string s
    for i in range(n):
        for j in range(i+1, n+1):
            substrings.add(s[i:j])
    
    # Check if any substring can be used to construct the given string s
    for substring in substrings:
        l = len(substring)
        if n % l == 0:
            if substring * (n // l) == s:
                return True
    
    return False

In this code, we first initialize an empty set called substrings to store all the possible substrings of the given string s. We also store the length of the given string s in the variable n.

Then, we use two loops to find all possible substrings of the given string s. The outer loop iterates over all possible starting indices of the substrings and the inner loop iterates over all possible ending indices of the substrings. We add each substring to the set substrings to avoid duplicate substrings.

After finding all possible substrings of the given string s, we iterate over each substring and check if it can be used to construct the given string s by appending multiple copies of the substring together. We first calculate the length of the substring and check if the length of the given string s is a multiple of the length of the substring. If this is true, we check if the given string s can be constructed by appending multiple copies of the substring together. If this is true, we return True.

If none of the substrings can be used to construct the given string s, we return False.

Overall, the time complexity of this approach is O(n^3), where n is the length of the given string s. This is because we are finding all possible substrings of the given string s, which takes O(n^2) time, and iterating over each substring, which takes O(n) time. The space complexity of this approach is also O(n^3), because we are storing all possible substrings in a set. However, in practice, the space complexity will be much less than O(n^3) because duplicate substrings will be removed in the set.

1