Repeated Substring Pattern

Difficulty: Easy | Acceptance: 48.20% | Paid: No Topics: String, String Matching

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

• Examples
• Constraints
• Brute Force
• String Concatenation Trick
• KMP Algorithm

Examples

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Input: s = "aba"
Output: false

Input: s = "abcabcabc"
Output: true
Explanation: It is the substring "abc" three times.

Constraints

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

Brute Force

Intuition We can iterate through all possible lengths of the repeating substring. For a string to be made of repeated substrings, the length of the substring must be a divisor of the total string length.

Steps

• Iterate through possible substring lengths i from 1 to n / 2.
• If n is divisible by i, extract the substring sub = s[0:i].
• Repeat this substring n / i times and check if it equals the original string s.
• If a match is found, return true. If the loop finishes without a match, return false.

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n // 2 + 1):
            if n % i == 0:
                sub = s[:i]
                if sub * (n // i) == s:
                    return True
        return False

Complexity

• Time: O(n²) - In the worst case, we iterate O(n) times and construct a string of length O(n) for comparison.
• Space: O(n) - To store the constructed string.
• Notes: Simple to implement but not the most efficient for very large strings.

String Concatenation Trick

Intuition If the string s is formed by repeating a substring, then concatenating s with itself (s + s) will contain s starting from an index other than 0 or n. Specifically, removing the first and last characters of s + s destroys the original s at the start and end, but if s is repeating, a copy of s will still exist in the middle.

Steps

• Concatenate the string with itself: double = s + s.
• Remove the first and last characters from double: double = double[1:-1].
• Check if the original string s is a substring of this modified double.
• If yes, return true; otherwise, return false.

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

Complexity

• Time: O(n) - String search/contains operation is typically linear.
• Space: O(n) - To store the concatenated string.
• Notes: Very concise and elegant solution.

KMP Algorithm

Intuition We can use the Longest Prefix Suffix (LPS) array from the Knuth-Morris-Pratt algorithm. The LPS array stores the length of the longest proper prefix of the string which is also a suffix. If the length of the last element in the LPS array (lps[n-1]) is greater than 0 and n is divisible by n - lps[n-1], then the string is made of a repeating substring.

Steps

• Compute the LPS array for the string s.
• Let len = lps[n-1] (length of the longest prefix which is also a suffix).
• Check if len > 0 and n % (n - len) == 0.
• If both conditions are true, return true; otherwise, return false.

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        lps = [0] * n
        
        # Build LPS array
        length = 0
        i = 1
        while i < n:
            if s[i] == s[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        longest_suffix = lps[-1]
        return longest_suffix > 0 and n % (n - longest_suffix) == 0

Complexity

• Time: O(n) - Building the LPS array takes linear time.
• Space: O(n) - To store the LPS array.
• Notes: Most efficient algorithmic approach for pattern matching problems.