# 1 line in Python

• ``````class Solution(object):
def repeatedSubstringPattern(self, s):
return any(s[:i] * (len(s) / i) == s for i in range(1, len(s)) if len(s) % i == 0)
``````

Time complexity is O(n1.5) because I do for O(n0.5) times (number of divisors of n) an O(n) operation, i.e., `s[:i] * (len(s) / d) == s`. Space complexity is O(n).

• Where is `d`?

• Should replace `d` by `i` and stop by `len(s) / 2 + 1`.

``````class Solution(object):
def repeatedSubstringPattern(self, s):
return any(s[:i] * (len(s) / i) == s for i in range(1, len(s) / 2 + 1) if len(s) % i == 0)
``````

• @agave Concise 1-line solution! Actually, if you could check both `d` and `len(s)/d` in the loop, you could cut the range to be `[1, sqrt(len(s))]` since all divisors in `[sqrt(len(s)), len(s)/2]` can be derived from previous range.

The O(n0.5) estimate for divisor count function d(n) is actually too conservative. I posted a time complexity analysis into a little bit more details to get a tighter bound. The overall complexity for this method is actually little o(n1+e) for any small e > 0.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.