459. Repeated Substring Pattern

EasyStringString Matching

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 returns True.

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 string s = "abab", after concatenation, we have a new string "abababab".
Using the .index() method, search for the original string s 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 of s starts) and see if s appears again within what follows. We're looking to find the beginning of the second s 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 string s 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 first s in the doubled string.
If the .index() method returns an index that is less than the length of s, the method repeatedSubstringPattern returns True. Otherwise, it returns False.

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 Evaluator

Example 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 string s is 6.
Searching for s: Next, we use the .index() method to search for the original string s 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 original s 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 string s 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 string s, according to our solution approach, the function repeatedSubstringPattern should return True. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know