Katkat
Back

Check Whether a String Is Built by Repetition

BeaconfireMachine Learning Engineer · Technical Screen
EasyMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to detect periodic string patterns using string manipulation or mathematical properties, specifically focusing on efficient substring identification.

Problem Statement

Given a non-empty string s, determine if it can be constructed by taking a substring of it and appending multiple copies of the substring together to construct the original string. You should return True if the string follows this pattern and False otherwise.

Function Signature

def is_repeated_pattern(s: str) -> bool:

Constraints

  • 1 <= s.length <= 10^4
  • s consists of lowercase English letters.

Examples

Example 1:

  • Input: s = "abab"
  • Output: True
  • Explanation: It is the substring "ab" repeated two times.

Example 2:

  • Input: s = "aba"
  • Output: False
  • Explanation: It cannot be constructed by repeating a substring.

Example 3:

  • Input: s = "abcabcabcabc"
  • Output: True
  • Explanation: It can be constructed by repeating "abc" four times or "abcabc" two times.

Edge Cases

  • Single character strings (e.g., "a") should return False as there is no smaller substring to repeat.
  • Strings with all identical characters (e.g., "aaaa") should return True.

Hints

Hint 1

If a string `S` is composed of a repeating substring `P`, then `S` must have a length divisible by the length of `P`.

Hint 2

Consider the property of string concatenation: if you concatenate `S` with itself (i.e., `SS`), and remove the first and last characters, does the original string `S` still exist within the new string?

Hint 3

If `S` is periodic, then `S` must be a substring of `(S + S)[1:-1]`.

Follow-up questions

  • What is the time complexity of your solution, and can you optimize it to run in O(n) time?
  • How would your approach change if you were asked to find the *shortest* possible repeating substring instead of just a boolean result?
  • How does the memory usage of your current approach scale with extremely large input strings?