Sponsored
Sponsored
One approach is to take a substring of the given string and repeatedly concatenate to check if it forms the original string. This involves iterating through possible substring lengths and using modular arithmetic to assess potential repeats.
Time Complexity: O(n^2). Space Complexity: O(n).
1def repeatedSubstringPattern(s):
2 n = len(s)
3 for i in range(1, n // 2 + 1):
4 if n % i == 0:
5 if s[:i] * (n // i) == s:
6 return True
7 return FalseThe code checks for substrings of increasing lengths up to half the size of the given string. If the length is divisible by the current substring length, it attempts to reconstruct the string by repeating the substring.
Another approach is using the property of doubled strings. By creating a new string by repeating the original and removing the first and last character, we can check if the original string exists within this new string.
Time Complexity: O(n). Space Complexity: O(n).
1classJava solution applies established string manipulations like concatenation and contains to conclude on repeated patterns.