PU Repeated Substring Pattern

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.

Example 1:

• Input: "abab"
• Output: True
• Explanation: It's the substring "ab" twice.

Example 2:

• Input: "aba"
• Output: False

Example 3:

• Input: "abcabcabcabc"
• Output: True
• Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

Python Solution 1:

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return s in s[1:] + s[:-1]

Python Solution 2:

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 3: return max(nums)
        origin_max = _max = max(nums)
        for _ in range(2):
            tmp = None
            for num in nums:
                if num < _max:
                    if tmp is None:
                        tmp = num
                    else:
                        tmp = max(tmp, num)
            if tmp is None: return origin_max
            _max = tmp
        return _max

Summary:

• https://discuss.leetcode.com/topic/68206/easy-python-solution-with-explaination/6
• The basic idea is:
  1. s in s[1:] + s[:-1] proves s == s1s2 == s2s1, if len(s1) == len(s2), problem solved.
  2. WLOG, let's say len(s1) < len(s2).
  3. s1s2 == s2s1 means s2 == s1s3 == s3s1. if len(s1) == len(s3), problem solved.
  4. Otherwise, s1 has to be shorter than s2.
     • The reason is that s can be represented as s1"s3s1s1"s3s1 and s3"s1s1s3"s1s1.
     • If s3 is shorter than s1, in the first step, s could be equal to s3s4 == s4s3, so it's false.
  5. s1s3 == s3s1 means s3 == s1s4 == s4s1.
  6. ...
  7. s == s1s1s1s1...s1sn == sns1...s1s1s1, until len(sn) == len(s1), problem solved.

LeetCode: 459. Repeated Substring Pattern