Repeated Substring Pattern Python Solution

Tested Python solution for LeetCode 459 with 28 pytest cases. Generate a practice environment with lcpy.

LeetCode 459, Easy. Topics: String, String Matching. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 28 parametrized pytest cases, and a playground notebook:

lcpy gen -n 459   # by problem number
lcpy gen -s repeated_substring_pattern   # by problem name

​

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.

​

Examples

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

Input: s = "aba"
Output: false

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

​

Constraints

• 1 <= s.length <= 10^4
• s consists of lowercase English letters.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(n)
    def repeated_substring_pattern(self, s: str) -> bool:
        n = len(s)
        lps = [0] * n
        length = 0
        for i in range(1, n):
            while length > 0 and s[i] != s[length]:
                length = lps[length - 1]
            if s[i] == s[length]:
                length += 1
            lps[i] = length
        longest_proper_suffix = lps[n - 1] if n > 0 else 0
        return longest_proper_suffix > 0 and n % (n - longest_proper_suffix) == 0

​

Complexity

Time	Space
O(n)	O(n)

​

Tags