Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

#### Brute force

If it can be composed by repeated strings `sub`

, then the length of `sub`

could be at most `len(s)/2`

and at least `1`

. So we can iterate through all possibles lengths and for each length, check whether we can construct the entire string by appending the repeated ones.

```
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
n = len(s)
for i in range(2,n+1): # divide s into i parts
if n%i==0:
l = n//i # the length of the repeated string
flag = True
for j in range(i-1):
if s[j*l:(j+1)*l] != s[(j+1)*l:(j+2)*l]:
flag = False
break
if flag:
return True
return False
```

#### Optimized

@rsrs3 provides a smarter way to deal with this problem. Given the string `s`

, we append another `s`

to it and now we have `ss`

. Then all we need to do is to find `s`

in `ss[1...n-1]`

.

Imaging `s`

is formed by repeated substrings such as `aa`

– by at least two repeated substrings.. Then `ss`

is `aaaa`

. When we take `ss[1...n-1]`

, the first and last repeated substrings are destroyed so it becomes `baab`

.

```
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
ss = (s+s)[1:-1]
return ss.find(s)!=-1
```

#### Reference

- https://leetcode.com/problems/repeated-substring-pattern/
- https://leetcode.com/problems/repeated-substring-pattern/discuss/94334/Easy-python-solution-with-explaination