{x}
blog image

Repeated Substring Pattern

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

 

Example 1:

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

Example 2:

Input: s = "aba"
Output: false

Example 3:

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

Solution Explanation

The problem asks whether a given string s can be formed by repeating a substring of itself multiple times. The solutions leverage a clever string manipulation technique.

Core Idea:

The solutions utilize the concept of concatenating the string with itself (s + s). If a repeated substring pattern exists, the concatenated string will contain the original string as a substring starting at index 1 (the second occurrence of the repeated pattern).

Algorithm:

  1. Concatenate: Create a new string str by concatenating the original string s with itself (s + s). This doubles the string, effectively overlapping the pattern.

  2. Search: Search for the original string s within str, starting the search from index 1. This skips the first occurrence of s within the concatenated string and searches for potential subsequent occurrences.

  3. Check Index: If s is found within str starting at index 1 before the end of the original string length, it means a repeated pattern exists. The index returned by .index() or .find() in Python, C++, and the other languages will be less than the length of the original s.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string s. String concatenation and the search operation both take linear time with respect to the string length.

  • Space Complexity: O(n). The concatenated string str requires linear space proportional to the length of s.

Code Explanation (Python):

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return (s + s).index(s, 1) < len(s)

This Python code directly implements the algorithm. (s + s) concatenates s with itself. .index(s, 1) searches for the first occurrence of s within the concatenated string, starting the search from index 1. The expression < len(s) checks if the found index is within the bounds of the original string's length (indicating a repeated pattern).

Other Languages:

The Java, C++, Go, TypeScript, and Rust solutions all follow the same core logic, adapting the string manipulation and search functions specific to each language. They all achieve the same time and space complexity. The core idea of concatenating and then searching for the original string at a later index remains consistent across all implementations.