Welcome to my personal website. I use this space to share some of my thoughts and software that I write in my free time. Sometimes I also publish photos. If you want to get in touch please use LinkedIn or Mastodon.
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.
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
Friedrich Ewald 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.