Friedrich Ewald My Personal Website

Leetcode: Repeated substring pattern

The task is to find out if a given string is comprised of multiple identical substrings. The first observation is that the substring cannot be longer than half of the length of the original string. The second observation is that the length of the total string has to be a multiple of the string that is tested, if it is not it can be discarded right away. Lastly, a string with the length of one can be discarded immediately. The main idea is to try out every string from size 1 to n/2+1 and break immediately of the next character is not the expected one. As an additional optimization, substrings whose length do not fit into the whole string can be discarded immediately.

class Solution:
  def repeatedSubstringPattern(self, s: str) -> bool:
    for length in range(1, int(len(s)/2)+1):
      # Discard strings with invalid length
      if len(s)%length != 0:
      ok = True
      # Create substring to test
      curr = s[:length]
      for char in range(length, len(s)):
        # Test character of substring. 
        # Only continue if character is as expected.
        if s[char] != curr[char%length]:
          ok = False
      if ok:
        return True
    # No valid substring found
    return False

if __name__ == '__main__':
  r = Solution().repeatedSubstringPattern
  print(r("aabaaba"), False)
  print(r("abcabc"), True)
  print(r("ababab"), True)
  print(r('abcxyz'), False)
  print(r('a'), False)
Runtime: 245 ms, faster than 34.66% of Python3 online submissions for Repeated Substring Pattern. Memory Usage: 14 MB, less than 59.35% of Python3 online submissions for Repeated Substring Pattern.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.