EasyNo. 0459

Repeated Substring Pattern — LeetCode 459 Python Solution

Pattern
Hash Map
Topics
String, String Matching
Reading time
2 min

The problem

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example

Input
s = "abab"
Output
true
Explanation
It is the substring "ab" twice.

Python solution

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

Complexity

Time
O(n)
Space · auxiliary
O(1) to O(n)

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 459. Repeated Substring Pattern is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 459. Repeated Substring Pattern?

LeetCode 459. Repeated Substring Pattern is rated Easy on LeetCode.

What topics does LeetCode 459. Repeated Substring Pattern cover?

LeetCode 459. Repeated Substring Pattern is tagged String and String Matching on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.