Vultr DocsLatest Content

Repeated Substring Pattern

Updated on 19 June, 2025
Repeated Substring Pattern header image

Problem Statement

The task is to determine if a given string, s, can be constituted entirely by repeating a substring of itself. A valid substring, when repeated one or more times, should recreate the string s without any additional characters or rearrangement. The crux of the problem lies in identifying if such a repeating pattern exists within the string that perfectly matches the entire string from start to finish.

Examples

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.

Approach and Intuition

The problem revolves around checking the repetitive nature of substrings within a string. Given the constraints and the nature of the problem, several observations and strategies can help solve this effectively:

  1. The length of the potential repeating substring must be a divisor of the total string length, s.length. If the length is not a divisor, the string cannot be evenly divided into substrings of equal length.

  2. If you concatenate the string s with itself and then remove the first and the last characters of this new string, any valid substring that can form s will necessarily appear within this modified version of the double string without its first and last characters. For example, with s = "abab", doubling and modifying it would result in "bababa". Since this contains "abab", it verifies that "abab" could be constructed by repeating a substring.

  3. Iterate through all possible lengths of the substring (which are divisors of s.length) and verify if repeating these substrings fulfills the formation of s. The straightforward approach checks for each divisor length whether continuous repetitions of the substring of that length result in the original string.

  4. While traversing through each possible substring length, once the first valid repeatable pattern is found, you can immediately conclude that the string can be constructed by some multiple of a substring. Conversely, if none of the subdivisions results in a valid pattern, the string cannot be broken down into repeated substrings as required.

This approach ensures that each scenario provided in the examples is covered efficiently and within the constraints set by the problem statement. The highlighted method addresses both verification of repetition and checks it in an optimized manner, focusing only on plausible substring lengths.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    bool hasRepeatedSubstring(string str) {
        string doubleStr = str + str;
        if (doubleStr.substr(1, doubleStr.length() - 2).find(str) != string::npos) return true;
        return false;
    }
};

The "Repeated Substring Pattern" problem checks if a string can be constructed by repeating some substring multiple times. The solution provided in C++ can be summarized as follows:

  • Create a new string, doubleStr, by concatenating the input string, str, with itself. This manipulation helps in identifying the cyclic pattern.
  • Check within doubleStr, excluding the first and the last character, to see if the original string, str, can be found. If str is found in this sliced version of doubleStr, this implies that str is made up of a repeated substring pattern.
  • The method hasRepeatedSubstring will return true if the original string is found within the modified double string, confirming the repeated pattern.

This method leverages the properties of string concatenation and searching to efficiently determine the presence of repeated patterns without explicitly identifying or counting the substrates.

java 
class Solution {
    public boolean hasRepeatedSubstring(String str) {
        String repeated = str + str;
        return repeated.substring(1, repeated.length() - 1).contains(str);
    }
}

The Java solution for checking whether a string can be constructed by repeating a substring involves an interesting approach:

  • Concatenate the input string with itself. This helps in identifying repeating pattern scenarios.
  • Use the substring method to avoid considering the first and last characters of this concatenated string which brings a shift and helps in pattern detection.
  • Utilize contains method to check if the original string appears within this modified version. If the original string can be found, it indicates that the string consists of repeating patterns.

This method effectively helps in determining if the entire string is a repeated pattern of a substring without explicitly identifying or extracting the potential repeating substring. Jump right into writing and testing your code using this method to handle similar challenges or to deepen understanding of string manipulation techniques in Java.

python 
class Solution:
    def checkRepeatedPattern(self, string: str) -> bool:
        duplicate = string + string
        return string in duplicate[1:-1]

The provided Python solution determines whether a string can be constructed by concatenating multiple instances of a substring. Here's an explanation of how the function operates:

  • The solution involves concatenating the input string with itself to create a new string named duplicate.
  • It then checks if the original string exists within the duplicate string, excluding its first and last characters. This is achieved through slicing in Python (duplicate[1:-1]).
  • If the original string exists in this manipulated version of duplicate, it means that the string comprises a repeated substring pattern and the function will return True.
  • If the original string does not exist within the modified duplicate, it indicates that the string does not have a repeating substring pattern, thus returning False.

This method effectively determines the repetitiveness of the substring pattern without explicitly identifying the substring itself. By checking inside the sliced version of the doubled string, the function cleverly utilizes the properties of string rotation and overlap, making it both versatile and efficient for this specific task.

Comments

No comments yet.