# Easy python solution with explaination

• Basic idea:

1. First char of input string is first char of repeated substring
2. Last char of input string is last char of repeated substring
3. Let S1 = S + S (where S in input string)
4. Remove 1 and last char of S1. Let this be S2
5. If S exists in S2 then return true else false
6. Let i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]
``````def repeatedSubstringPattern(self, str):

"""
:type str: str
:rtype: bool
"""
if not str:
return False

ss = (str + str)[1:-1]
return ss.find(str) != -1
``````

• thank you for your amzaing solution!!!!

• @rsrs3 Thanks for your amazing solution! Could you share your thoughts on how to technically prove this solution is correct? It passed all the test cases, but I still have no idea why it works.

• Good solution @rsrs3 but as @Eastknight said it would be nice if we know why this works.

• Let's say `T = S + S`.
"`S is Repeated => From T[1:-1] we can find S`" is obvious.

If from `T[1:-1]` we found `S` at index `p-1`, which is index `p` in `T` and `S`.
let `s1 = S[:p]`, `S` can be represented as `s1s2...sn`, where `si` stands for substring rather than character.
then we know `T[p:len(S) + p] = s2s3...sn-1sns1 = S = s1s2...sn-2sn-1sn`.
So `s1 = s2, s2 = s3, ..., sn-1 = sn, sn = s1`,Which means S is Repeated.

edit:
I should fix this because `len(si) == len(sj)` has not be proved. The procedure becomes complicated :-(
Let `s1 = S[:p]`, `S` can be represented as `s1X1`.
then `S = X1s1 = s1X1 (A)`.

1. `len(X1) < len(s1)` is false because if so we should find S in T[1:-1] at index len(X1) rather than len(s1) = p.

2. `len(X1) == len(s1) and (A)` => `X1 = s1` => S is Repeated.

3. `len(X1) > len(s1) and (A)` => X1 has prefix s1 so can be represented as `s1X2`.
`X1 = s1X2 and (A)` => `s1X2s1= s1s1X2` =>`X2s1 = s1X2 (B)`.
`len(X2) < len(s1)` is false because if so `(A) and (B)` => `S = X2s1s1 = s1s1X2` and we should find S at index len(X2) rather than p.

As long as `len(Xi-1) > len(s1)`, we can get `Xis1 = s1Xi` through the prefix step and prove `len(Xi) < len(s1)` is false through the index step. Eventually we can get a `Xn`, `len(Xn) == len(s1) and Xns1 = s1Xn` => `Xn = s1` => `S = s1X1 = s1s1X2 = ... = s1s1...s1Xn-1 = s1s1...s1s1Xn` => S is Repeated.

• Wow that's nice. But the code can be nicer, at least better use the `in` operator:

``````def repeatedSubstringPattern(self, str):
return str in (2 * str)[1:-1]``````

• @QuentinLewes thanks! this makes it clear!

• This post is deleted!

• Awesome!!!! Best solution for this problem!!

• @QuentinLewes
Perhaps a simpler proof for `From T[1:-1] we can find S => S is Repeated`:
Suppose `S = s1s2`, where `s1 in S[1:]` and `s2 in S[:-1]`, which means `S = s1s2 = s2s1` and WLOG we can assume `len(s1) < len(s2)`.
We only need to prove that `s2 = s1...s1`. This is directly from `s1s2 = s2s1` as well (if you compare char by char).

• This post is deleted!

• The explanation for why that works is pretty straight forward.

Consider a string `S="helloworld"`. Now, given another string `T="lloworldhe"`, can we figure out if `T` is a rotated version of `S`? Yes, we can! We check if `S` is a substring of `T+T`.

Fine. How do we apply that to this problem? We consider every rotation of string `S` such that it's rotated by `k` units `[k < len(S)]` to the left. Specifically, we're looking at strings "`elloworldh", "lloworldhe", "loworldhel", etc...`

If we have a string that is periodic (i.e. is made up of strings that are the same and repeat `R` times), then we can check if the string is equal to some rotation of itself, and if it is, then we know that the string is periodic. Checking if `S` is a sub-string of `(S+S)[1:-1]` basically checks if the string is present in a rotation of itself for all values of `R` such that `0 < R < len(S)`.

• Wow. It is super smart. The best solution for the problem.
Let me make a note for future reference.

If the string S has repeated block, it could be described in terms of pattern.
`S = SpSp` (For example, `S` has two repeatable block at most)
If we repeat the string, then `SS=SpSpSpSp`.
Destroying first and the last pattern by removing each character, we generate a new `S2=SxSpSpSy`.

If the string has repeatable pattern inside, `S2` should have valid `S` in its string.

• @QuentinLewes thanks, the explanation is clear and easy to follow.

• This post is deleted!

• perfect solution ! thanks for contribution!

• Simple and very good solution.

Not only for python, ur code helps everyone .. thanku

• Here is a java solution of the same idea:

``````public boolean repeatedSubstringPattern(String s) {
String c = (s + s).substring(1, s.length() + s.length() - 1);
return c.indexOf(s) != -1;
}
``````

• This post is deleted!

• This post is deleted!

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