Scale Engineer

Repeated Substring Pattern

Easy
#0446Time: O(n^2) - The outer loop runs `n/2` times. For each length `l`, the inner loop performs `n/l - 1` substring comparisons. Each comparison of length `l` takes `O(l)` time. The total work for a given `l` is `(n/l) * O(l) = O(n)`. Since the outer loop runs `O(n)` times, the total complexity is `O(n^2)`.Space: O(n) - In each iteration, we create a substring `sub` of length `l`. The maximum length of `l` is `n/2`. In Java, `substring` creates a new string, so the space complexity is dominated by the storage for these substrings.1 company
Patterns
String Matching
Data structures
String
Companies
Myntra

Prompt

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

 

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.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

Approaches

4 approaches with complexity analysis and trade-offs.

This approach tests every possible length for the repeating substring. A valid substring must have a length l that is a divisor of the total string length n. We can iterate through all possible lengths l from 1 up to n/2. For each l, we check if the entire string s is formed by repeating the prefix of length l.

Algorithm

  1. Get the length of the string, n.
  2. Iterate l from 1 to n / 2.
  3. If n is divisible by l: a. Extract the substring sub = s.substring(0, l). b. Assume the pattern holds (match = true). c. Iterate j from l to n - l with a step of l. d. If s.substring(j, j + l) is not equal to sub, set match = false and break the inner loop. e. If match is still true after the inner loop, return true.
  4. If the outer loop finishes, return false.

Walkthrough

The algorithm iterates through possible substring lengths l from 1 to s.length() / 2. For a length l to be a candidate, we first check if the total length n is divisible by l. If it is, we extract the first substring of length l, let's call it sub. We then verify if the rest of the string s consists of repetitions of sub. This is done by comparing sub with every subsequent block of l characters in s. If all blocks match sub, we have found a valid pattern and return true. If we find a mismatch, we move on to the next possible length. If the loop completes without finding any such pattern, we return false.

class Solution {    public boolean repeatedSubstringPattern(String s) {        int n = s.length();        for (int l = 1; l <= n / 2; l++) {            if (n % l == 0) {                String sub = s.substring(0, l);                boolean match = true;                for (int j = l; j < n; j += l) {                    if (!s.substring(j, j + l).equals(sub)) {                        match = false;                        break;                    }                }                if (match) {                    return true;                }            }        }        return false;    }}

Complexity

Time

O(n^2) - The outer loop runs `n/2` times. For each length `l`, the inner loop performs `n/l - 1` substring comparisons. Each comparison of length `l` takes `O(l)` time. The total work for a given `l` is `(n/l) * O(l) = O(n)`. Since the outer loop runs `O(n)` times, the total complexity is `O(n^2)`.

Space

O(n) - In each iteration, we create a substring `sub` of length `l`. The maximum length of `l` is `n/2`. In Java, `substring` creates a new string, so the space complexity is dominated by the storage for these substrings.

Trade-offs

Pros

  • Simple to understand and implement.

  • A straightforward, direct translation of the problem statement.

Cons

  • Inefficient for long strings, as it checks many unnecessary lengths.

  • Likely to result in a 'Time Limit Exceeded' error on competitive programming platforms for larger inputs.

Solutions

class Solution {public  boolean repeatedSubstringPattern(String s) {    String str = s + s;    return str.substring(1, str.length() - 1).contains(s);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem