#459

Easy

LeetCode Problem Workspace

Repeated Substring Pattern

Check if a string can be constructed by repeating a substring using string matching techniques.

Problem Statement

You are given a string s. Your task is to determine whether this string can be constructed by repeating a substring. The substring should appear multiple times and fill the entire string without any leftover characters.

For example, in the string s = "abab", the substring "ab" repeats twice to form the string. In contrast, a string like "aba" cannot be formed by repeating any substring.

Examples

Example 1

Input: s = "abab"

Output: true

It is the substring "ab" twice.

Example 2

Input: s = "aba"

Output: false

Example details omitted.

Example 3

Input: s = "abcabcabcabc"

Output: true

It is the substring "abc" four times or the substring "abcabc" twice.

Constraints

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

Solution Approach

String Concatenation Approach

A simple method involves concatenating the string with itself, and then checking if the original string appears within this concatenated version. This works because a repeating substring will always show up in the concatenated string excluding the first and last character.

Pattern Matching via KMP

KMP (Knuth-Morris-Pratt) can be applied to find if a repeating pattern exists in the string. By computing the prefix array, we can identify the longest prefix that also functions as a suffix, which helps in detecting a repeating substring.

Mathematical Approach

Another approach involves checking if the length of the string is divisible by a potential substring length. If the division is exact, then repeating the substring that length results in the original string. This method requires iterating over possible lengths.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. For string concatenation, it is O(n) where n is the length of the string. The KMP approach also runs in O(n) due to the linear scan for pattern matching. The mathematical approach could vary from O(n) to O(n^2) depending on the checking mechanism used for each substring length.

What Interviewers Usually Probe

The candidate is able to identify the pattern and suggest multiple methods for solving it.
The candidate considers both the time and space complexity in their solution approach.
The candidate explains string manipulation techniques clearly and concisely.

Common Pitfalls or Variants

Common pitfalls

The candidate might suggest overly complicated solutions when a simpler method, such as string concatenation, suffices.
Failing to account for edge cases like non-repeating strings or very short strings.
Overlooking the time complexity of the solution, especially when using nested loops or unnecessary operations.

Follow-up variants

Check if a string can be constructed from a substring with a limited number of repetitions.
Determine the longest repeating substring that can form a string when repeated.
Extend the problem to multiple substrings and check if they can collectively form the given string.

FAQ

What is the time complexity for the Repeated Substring Pattern problem?

The time complexity can vary. For the string concatenation approach, it is O(n), while the KMP approach also runs in O(n). More complex approaches might take longer.

How can I optimize my solution for the Repeated Substring Pattern problem?

Consider using KMP for efficient pattern matching, or the string concatenation method, which is simple and works well for most cases.

What is the pattern behind the Repeated Substring Pattern problem?

The problem follows the string matching pattern, where we try to identify repeating substrings within the string and check if they can construct the original string.

What edge cases should I consider for this problem?

Make sure to handle strings that are too short, non-repeating strings, and strings that might only seem to repeat a substring at first glance.

What are some variations of the Repeated Substring Pattern problem?

Variants could involve checking for a specific number of repetitions, finding the longest repeating substring, or working with multiple substrings forming the string.

terminal

Solution

Solution 1

#### Python3

1

2

3

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

Continue Practicing

#686 repeated string match #214 shortest palindrome #796 rotate string