https://leetcode.com/problems/repeated-substring-pattern

Nice and easy problem, which can be solved in different ways.

Solution 1

Just check all posible divisors of lenght of s, replicate them and compare them with original string. If we have found it, we return True, if we reached the end and we did not find any, we return False.

Complexity: time complexity is O(n*sqrt(n)), because we have no more than O(sqrt(n)) divisors of number n (we can split them into pairs, where one number in pair will be <sqrt(n). Space compexity is O(n).

class Solution:
    def repeatedSubstringPattern(self, s):
        N = len(s)
        for i in range(1, N//2+1):
            if N % i == 0 and s[:i]* (N//i) == s:
                return True
        return False

Solution 2

But wait, there is more! There is in fact very short and interesting solution. Let us replicate our sting, remove first and last elements and try to find original string: for example:

s = abcdabcd, then we have bcdabcdabcdabc, where we can find abcdabcd inside. It is a bit more difficult to prove, that opposite is true: if we found substring it will mean that we have repeated substring pattern. I will add proof a bit later.

Complexity: time complexity is basically O(n), because we can find substrings in linear time. In python function in will work, using Boyer-Moore algorithm, which is in average work in linear time (if you do not like average, you can use KMP, which have worst linear time, not average). Space complexity is O(n).

return s in (s+s)[1:-1]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0459