Problem Description

Given a non-empty string s, determine if it can be constructed by taking a substring of it and appending multiple copies of the substring together. In other words, check if s is a repeated substring pattern. For example, for s = "abab", the answer is true because it is "ab" + "ab". For s = "aba", the answer is false.

• Input: A string s of length between 1 and 10,000, consisting only of lowercase English letters.
• Output: Return true if s can be constructed by repeating a substring, otherwise false.
• Constraints: The substring must not be equal to the entire string, and must repeat at least once.

Thought Process

The first idea that comes to mind is to try every possible substring length and see if repeating it forms the original string. This would involve checking all possible substring lengths from 1 up to half of the string's length, since a substring longer than half can't repeat at least twice.

However, this brute-force approach can be slow for long strings. To optimize, we can use mathematical properties and string manipulation techniques. For instance, if the length of s is divisible by some k, then s could be made by repeating s[0:k] exactly n // k times. We need to check only these lengths.

There is also a clever trick: if we double the string (i.e., s + s) and remove the first and last character, the original string s should be found inside this new string if and only if s is a repeated pattern. This is because the repeated pattern will overlap in the doubled string.

Solution Approach

Let's break down the steps for the efficient solution:

1. String Doubling Trick:
   • Create a new string t = s + s.
   • Remove the first and last character from t, resulting in t'.
   • If s appears in t', then s is constructed by repeating a substring. Otherwise, it is not.
2. Why does this work?
   • If s is made by repeating a substring, then when you double it and remove the first and last character, the repeated pattern will cause s to appear somewhere inside.
   • If s is not a repeated pattern, then it will not appear in the modified double string.
3. Alternative Brute Force (for understanding):
   • For every possible substring length k from 1 to len(s) // 2:
   • If len(s) % k == 0, check if repeating s[0:k] len(s)//k times equals s.
   • If any such k works, return true. Otherwise, return false.

The string doubling trick is preferred for its conciseness and efficiency.

Example Walkthrough

Let's take s = "abab" as an example:

• Double the string: "abab" + "abab" = "abababab"
• Remove first and last character: "bababab"
• Check if "abab" appears in "bababab": Yes, at index 1.
• Therefore, the function returns true.

Now, try s = "aba":

• Double the string: "abaaba"
• Remove first and last character: "baab"
• Check if "aba" appears in "baab": No.
• Therefore, the function returns false.

Code Implementation

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (s + s)[1:-1]
      

class Solution {
   public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        return t.substr(1, t.size() - 2).find(s) != string::npos;
    }
};
      

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String t = s + s;
        return t.substring(1, t.length() - 1).contains(s);
    }
}
      

var repeatedSubstringPattern = function(s) {
    let t = s + s;
    return t.slice(1, -1).includes(s);
};
      

Time and Space Complexity

Brute-force approach:

• For each possible substring length k, we may have to build a repeated string of length n and compare it to s.
• There are up to n/2 such k values.
• Time Complexity: O(n²), where n is the length of s.
• Space Complexity: O(n) for the repeated string.

• Doubling the string and slicing takes O(n) time and space.
• Searching for s in the doubled string (with first and last char removed) is O(n).
• Time Complexity: O(n)
• Space Complexity: O(n)

Summary

The "Repeated Substring Pattern" problem can be solved efficiently using a clever string manipulation trick. By doubling the string, removing the first and last characters, and checking if the original string is present, we can determine in linear time whether the string is made from repeating a substring. This approach is elegant, concise, and avoids unnecessary brute-force checks, making it ideal for large input strings.