Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0459 - Repeated Substring Pattern
    0459 - Repeated Substring Pattern
    0459 - Repeated Substring Pattern
    0459 - Repeated Substring Pattern

    0459 - Repeated Substring Pattern

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/repeated-substring-pattern/

    Solution 1 - String Concatenation Trick

    Given a string s, check if it can be constructed by repeating a substring. The key insight: if s has a repeating pattern, then s will appear in (s + s)[1:-1] (the doubled string with the first and last characters removed). This works because removing those characters destroys the original boundaries, so s can only reappear if an internal repeating structure exists.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 2 - Brute Force Substring Check

    Try every possible substring length from 1 to len(s) // 2. For each candidate length that evenly divides len(s), check if repeating that substring fills the entire string. Return True on the first match.

    TimeComplexity:O(n2)TimeComplexity: O(n^2)TimeComplexity:O(n2)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0459.1 - Solution 1 - String Concatenation Trick """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def repeatedSubstringPattern(self, s: str) -> bool:
        """Repeated Substring Pattern Function"""
        return s in (s + s)[1:-1]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().repeatedSubstringPattern("abab"))           # True
    print(Solution().repeatedSubstringPattern("aba"))            # False
    print(Solution().repeatedSubstringPattern("abcabcabcabc"))   # True
    print(Solution().repeatedSubstringPattern("a"))              # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0459.2 - Solution 2 - Brute Force Substring Check """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def repeatedSubstringPattern(self, s: str) -> bool:
        """Repeated Substring Pattern Function"""
        n = len(s)

        for i in range(1, n // 2 + 1):
            if n % i == 0:
                substring = s[:i]
                if substring * (n // i) == s:
                    return True

        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().repeatedSubstringPattern("abab"))           # True
    print(Solution().repeatedSubstringPattern("aba"))            # False
    print(Solution().repeatedSubstringPattern("abcabcabcabc"))   # True
    print(Solution().repeatedSubstringPattern("a"))              # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()