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)

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()

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(n^2)

SpaceComplexity: O(n)

""" 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()

0459 - Repeated Substring Pattern

Solution 1 - String Concatenation Trick

Solution 2 - Brute Force Substring Check