Leetcode 459: Repeated Substring Pattern

Input: The input consists of a string `s`.

Example: s = 'abab'

Constraints:

• 1 <= s.length <= 10^4

• s consists of lowercase English letters.

Output: Return true if the string can be constructed by repeating a substring multiple times, otherwise return false.

Example: Output: true

Constraints:

• The output should be a boolean indicating whether the string can be repeated from a substring.

Goal: The goal is to check if a non-empty substring exists that can be repeated to form the string.

Steps:

• 1. Concatenate the string with itself to find potential repeating substrings.

• 2. Check if the original string appears in the concatenated string, excluding the first and last character.

• 3. If found, return true, otherwise return false.

Goal: The string's length can be up to 10^4, so the solution needs to be efficient.

Steps:

• Handle strings with lengths up to 10^4.

• The string consists only of lowercase English letters.

Assumptions:

• The input string is non-empty and consists only of lowercase English letters.

• Input: s = 'abab'

• Explanation: The string 'abab' can be formed by repeating the substring 'ab'.

• Input: s = 'abcabcabc'

• Explanation: The string 'abcabcabc' can be formed by repeating the substring 'abc'.

Approach: The solution involves checking if the string can be formed by repeating a substring using string manipulation.

Observations:

• By concatenating the string with itself, we create potential repeated patterns.

• If the string is repeatable, we can find the original string within the concatenated version, excluding the first and last character.

Steps:

• 1. Concatenate the string `s` with itself.

• 2. Search for the original string `s` within the concatenated string, excluding the first and last character.

• 3. If the string is found, return true, otherwise return false.

Empty Inputs:

• An empty string is not allowed as per the constraints.

Large Inputs:

• Ensure that the solution works efficiently for strings up to the maximum length of 10^4.

Special Values:

• Consider strings that are already repeating, such as 'ababab'.

Constraints:

• Handle large inputs efficiently with time complexity O(n).

bool repeatedSubstringPattern(string str) {
    return (str + str).substr(1, str.size() * 2 - 2).find(str)!=-1;
}

1 : Function Definition

bool repeatedSubstringPattern(string str) {

Defines the `repeatedSubstringPattern` function, which takes a string `str` and returns a boolean indicating whether the string can be formed by repeating a substring.

2 : String Manipulation

    return (str + str).substr(1, str.size() * 2 - 2).find(str)!=-1;

Concatenates the string `str` with itself and uses the `substr` method to remove the first and last characters. Then, it checks if the original string exists within the modified string. If found, it returns `true`, indicating the string can be formed by repeating a substring.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) as we only perform a string concatenation and search operation.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the concatenation of the string with itself.

Leetcode 459: Repeated Substring Pattern

Solution to LeetCode 459: Repeated Substring Pattern Problem

Explore →