Problem
Given a string s
, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Examples
Example 1:
Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.
Example 2:
Input: s = "aba"
Output: false
Example 3:
Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.
Solution
Method 1 - Create Multiple Substring and Checking Till length/2
Here is the approach:
- The length of the repeating substring must be a divisor of the length of the input string.
- Search for all possible divisors of
str.length()
, starting fromlength / 2
. - If
i
is a divisor oflength
, repeat the substring from0
toi
the number of timesi
fits intos.length
. - If the repeated substring equals the input
str
, returntrue
.
For example, for the string s = "abcabcabcabc"
, the half string is abcabc
. Since the first half and the second half are identical, we return true.
Code
Java
public class Solution {
public boolean repeatedSubstringPattern(String str) {
int l = str.length();
for(int i = l / 2; i >= 1; i--) {
if (l % i != 0) {
continue;
}
int m = l / i;
String subS = str.substring(0, i);
StringBuilder sb = new StringBuilder();
for (int j = 0; j < m; j++) {
sb.append(subS);
}
if (sb.toString().equals(str)) {
return true;
}
}
return false;
}
}
Python
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
l: int = len(s)
for i in range(l // 2, 0, -1):
if l % i == 0:
m: int = l // i
sub_s: str = s[:i]
if sub_s * m == s:
return True
return False
Complexity
- ⏰ Time complexity:
O(n^2)
. The outer loop runsO(n/2)
times, and the inner concatenation could runO(n)
in the worst case. - 🧺 Space complexity:
O(n)
. Due to creating substrings and the StringBuilder in Java or equivalent operations in Python.