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:

1
2
3

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Example 2:

1
2

Input: s = "aba"
Output: false

Example 3:

1
2
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:

  1. The length of the repeating substring must be a divisor of the length of the input string.
  2. Search for all possible divisors of str.length(), starting from length / 2.
  3. If i is a divisor of length, repeat the substring from 0 to i the number of times i fits into s.length.
  4. If the repeated substring equals the input str, return true.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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 runs O(n/2) times, and the inner concatenation could run O(n) in the worst case.
  • 🧺 Space complexity: O(n). Due to creating substrings and the StringBuilder in Java or equivalent operations in Python.