September 09, 2020 ### Description:

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

Example 1:

```Input: "abab"
Output: True
Explanation: It's the sub-string "ab" twice.
```

Example 2:

```Input: "aba"
Output: False
```

Example 3:

```Input: "abcabcabcabc"
Output: True
Explanation: It's the sub-string "abc" four times. (And the sub-string "abcabc" twice.)```

### Solution 1:

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

class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
length = len(s)
if (not length):
return False

mid = length // 2
stack = list()
for char in s[:mid + 1]:
if (not stack):
stack.append(char)
else:
# if length of string is not multiple
# length of sub-string skip
if (length % len(stack) != 0):
stack.append(char)
continue

# if current letter and first letter of the
if (not stack == char):
stack.append(char)
else:
status = self.checkRepetetion(s[len(stack):], stack)
if (status):
return True
stack.append(char)
return False

def checkRepetetion(self, s, snip):
if (s and ''.join(snip) == s[:len(snip)]):
s = s[len(snip):]
else:
return False

# If string becomes empty
if (not s):
return True
return self.checkRepetetion(s, snip)``````

### Explanation:

Our objective is to find out whether the given string can be formed by repeating any one of its sub-strings. In the first example given in the description, the string s is 'abab'. This can be formed by repeating its sub-string 'ab'. There may be multiple ways in which we can achieve this. The most crude way to do this is by brute force.

i.e. for every sub-string possible, check whether we can generate the complete string by repeating it. The steps in solving this for the example 1 are as follows,

• step 1: Take the first smallest prefix. i.e. 'a'
• Step 2: Check whether we can generate the original string by repeating it. We can achieve this by popping the matched character from the beginning of the string, repeatedly.
• Step 3: If no string left after completing sub-string match, then return True.
• Step 4: Take the next smallest prefix possible and repeat from step 2...

This algorithm takes O(n2) in the worst case scenario. If we observe the problem very closely, there is a pattern that we can use to identify the repeated sub-string pattern that makes the given string. Assume that the string formed by repeating a sub-string pattern Sp twice. i.e. s = SpSp.

Then s + s = ss = SpSpSpSp. Here if we deform the start and end patterns,

i.e. SmSpSpSm. If we are able to find string 's' in the result, then the answer is 'True' else 'False'. This implementation has worst case complexity as O(n) and we can implement it with in two lines of code.

### Solution 2 (Best Solution):

``````class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
s_twice = s + s
if(s in s_twice[1:-1]):
return True
return False``````

### Evaluation: Recent Posts
Categories
Archive
Tags