459. Repeated Substring Pattern
Problem Description
The problem asks us to determine whether a given string s
can be formed by taking a substring of itself and repeating that substring multiple times consecutively to create the string. For example, the string "abab" can be created by repeating the substring "ab" twice, so the output should be True
. However, the string "aba" cannot be created by repeating any of its substrings, thus the output should be False
.
Intuition
The intuition behind the solution is based on the idea that if the string s
can be constructed by repeating a substring, then you would be able to find the beginning of the original string s
somewhere in the middle of the string when the string is doubled. This is because the repeating pattern would continue in the doubled string and the start of the second copy of s
in the doubled string would align with the start of some repeat of the pattern within the first copy.
The solution approach is to concatenate the string s
with itself, forming (s + s)
, and then searching for the original string s
inside this new string starting from index 1. By doing this, we intentionally skip the very beginning of the first s
to ensure we are not merely finding the original first occurrence of s. If s
is a repeated pattern, we expect to find s
starting at some position before we reach the end of the doubled string's first half. If s
is found and the index is less than the length of s
, it means s
can indeed be constructed by repeating a substring.
For example, for s = "abab"
:
- Doubling
s
gives us "abababab". - Searching for "abab" inside the double string starting from the second character gives us an index of 2.
- Since 2 is less than the length of
s
, which is 4, the function returnsTrue
.
The Python code (s + s).index(s, 1) < len(s)
implements this logic concisely. The method .index()
will either return the index where s
is found in (s + s)
, or raise a ValueError if s
is not found, which means the whole chain evaluates to False
.
Solution Approach
The implementation of the solution involves a simple but clever use of string manipulation and searching. The algorithm doesn't explicitly use complex data structures or searching patterns but leverages the built-in methods in Python.
Here's a step-by-step breakdown of the solution approach:
-
Concatenate the input string
s
with itself using the+
operator. This creates a new string which is twice the length of the original string. For an input strings = "abab"
, after concatenation, we have a new string"abababab"
. -
Using the
.index()
method, search for the original strings
within the concatenated string(s + s)
, starting from index 1. Why index 1? Because we want to skip the first character of the concatenated string (which is where the first occurrence ofs
starts) and see ifs
appears again within what follows. We're looking to find the beginning of the seconds
in the doubled string. -
If
s
is found and its starting index is less than the length of the original string, it confirms that the original strings
can be created by repeating a substring. It means that the pattern started at least once more somewhere after the first character of the concatenated string, but before we reached the end of what would've been the firsts
in the doubled string. -
If the
.index()
method returns an index that is less than the length ofs
, the methodrepeatedSubstringPattern
returnsTrue
. Otherwise, it returnsFalse
.
The elegance of this solution lies in its use of string self-concatenation to simulate the process of repeating a substring—if s
indeed can be constructed by such repetition, this pattern will reveal itself through the concatenation and be evident by the new occurrence of s
within (s + s)
.
In this Python code: (s + s).index(s, 1) < len(s)
, s
is doubled, we use the .index()
method to search for the first occurrence of the original s
starting from index 1, and we check if the index found is less than the length of the original string s
. The comparison result (True or False) is then returned directly.
This method does not require extra space for another data structure, and it effectively utilizes the repeating nature of the string to check for the repeated substring pattern.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example using the string s = "bcbcbc"
.
-
Concatenation: First, we concatenate the string to itself, resulting in
(s + s) = "bcbcbcbcbcbc"
. The length of the original strings
is 6. -
Searching for
s
: Next, we use the.index()
method to search for the original strings
within this new doubled string. We must start searching from position 1, i.e., from the second character, in order to skip the obvious match at the beginning of the doubled string. -
Index Found: When we do this search, we find that the index where
s
appears again within the doubled string(s + s)
is at position 2. This is because the substring "bcbc" from the originals
can be seen starting at index 2 and again at index 4 and 6 in the doubled string. -
Evaluation: The index 2 is less than the length of the original string
s
(which is 6), indicating that the strings
can indeed be constructed by repeating a substring ("bcbc" in this case). -
Conclusion: Since the
.index()
method returned an index (2) less than the length of the original strings
, according to our solution approach, the functionrepeatedSubstringPattern
should returnTrue
. This correctly reflects that the string "bcbcbc" can be formed by repeating the substring "bcbc" multiple times consecutively.
Solution Implementation
1class Solution:
2 def repeatedSubstringPattern(self, s: str) -> bool:
3 # Duplicate the string 's' by concatenating it with itself.
4 # This is a common trick to identify if the string contains a repeating pattern.
5 double_s = s + s
6
7 # Try to find the original string 's' within this doubled string,
8 # but starting the search from index 1 (not from the beginning)
9 # to bypass the first occurrence of the string 's'.
10 index_in_double_s = double_s.index(s, 1)
11
12 # If 's' is found in double_s before the end of the original string 's',
13 # then it means 's' has a repeating pattern within itself.
14 # In the original string, the second occurrence must start before the string ends
15 # if it is a repeated pattern.
16 return index_in_double_s < len(s)
17
18# The method 'repeatedSubstringPattern' is part of the 'Solution' class, and it
19# checks if the given string 's' consists of one or more repetitions of a substring.
20
1class Solution {
2
3 // Function to check if the string contains a repeating substring pattern.
4 public boolean repeatedSubstringPattern(String str) {
5 // Concatenate the string with itself.
6 String doubledString = str + str;
7
8 // Check if the concatenated string, with the first and last characters removed,
9 // still contains the original string.
10 // This technique works because if the original string is composed of repeated
11 // patterns, then by removing the first and the last characters, and still being able
12 // to find the original string ensures that the pattern is indeed repeating.
13 return doubledString.substring(1, doubledString.length() - 1).contains(str);
14 }
15}
16
1#include <string>
2using std::string;
3
4class Solution {
5public:
6 // Function to check if the input string is composed of one or more repetitions of a substring.
7 bool repeatedSubstringPattern(string str) {
8 // Concatenate the input string with itself.
9 string doubledString = str + str;
10
11 // Try to find the original string inside the doubled string, starting from index 1.
12 // The idea is that if the original string is a repeating pattern, the doubling
13 // will cause overlaps of this pattern, and the original string should reoccur before
14 // the end of the first instance of itself in the concatenation.
15
16 size_t position = doubledString.find(str, 1); // Start the search at index 1
17
18 // If the original string is found in the concatenated string at a position that is less
19 // than the size of the original string, it means there is a repeating pattern.
20 // We also exclude the trivial case of finding the first occurrence of the string
21 // in the doubled string, which will always happen at index str.size().
22
23 // Return true if we find the pattern, which indicates the input is a repetition.
24 // Otherwise, return false.
25 return position < str.size();
26 }
27};
28
1function repeatedSubstringPattern(str: string): boolean {
2 // Double the input string and remove the first and last characters
3 const doubledString = (str + str).slice(1, -1);
4
5 // Check if the modified (doubled and trimmed) string includes the original string
6 // If it does, it implies the original string is composed of repeated substrings
7 return doubledString.includes(str);
8}
9
10// Usage of the function
11// const result = repeatedSubstringPattern("abab"); // Should return true
12// console.log(result);
13
Time and Space Complexity
The time complexity of the code is O(n)
where n
is the length of string s
. This is because string concatenation (s + s)
takes O(n)
time and the subsequent .index()
method call will in the worst-case scan the entire length of the concatenated string which is 2n
. Still, since the index is being found for a substring that we know exists (and is actually the prefix of the concatenated string), it will typically be found near the start of the second half of the concatenated string, often making the practical runtime much lower. However, for worst-case time complexity estimation, we consider it as O(n)
.
The space complexity of the code is also O(n)
because a new string (s + s)
is being created that is twice the length of the original string s
.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.