September 09, 2020
[LeetCode#459] Repeated Substring Pattern

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
                # sub-string don't match, then skip to the next letter
                if (not stack[0] == 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:

Repeated Sub-string Pattern Time complexity