Repeated Substring Pattern

Easy
217.

Repeated Substring Pattern

Repeated Substring Pattern is an easy coding problem on strings and string matching, asked in Amazon, Google, Microsoft and Myntra interviews.

Given a string s, return true if it can be built by taking one of its proper substrings and concatenating multiple copies of it.

Example 1

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

Example 2

Input
s = "aba"
Output
false

Example 3

Input
s = "abcabcabcabc"
Output
true
Explanation
It is "abc" four times.

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Repeated Substring Pattern — Solution in Python, Java & C++

Repeated Substring Pattern solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Repeated Substring Pattern is an easy coding problem on strings and string matching, asked in Amazon, Google, Microsoft and Myntra interviews.

Problem statement

Given a string s, return true if it can be built by taking one of its proper substrings and concatenating multiple copies of it.

Example 1

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

Example 2

Input: s = "aba"
Output: false

Example 3

Input: s = "abcabcabcabc"
Output: true
Explanation: It is "abc" four times.

Constraints

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

Hints for Repeated Substring Pattern

  1. Hint 1

    The repeating unit's length must divide the string's length, and be at most half of it.

  2. Hint 2

    Test each such length by comparing every block against the first one.

  3. Hint 3

    A neat trick: s has this property exactly when it appears inside (s + s) with the first and last characters removed.

How to solve Repeated Substring Pattern

The repeating unit's length must divide n and be at most n/2; for each such length, check whether repeating the prefix reproduces the string.

Approach

  1. For each length from 1 to n // 2, skip it unless it divides n.
  2. Build s[:length] repeated n / length times and compare with s.
  3. Return true on the first match, false if none.

Why it works

If s is u repeated k >= 2 times then |u| divides n, |u| <= n/2, and u is precisely the prefix of that length — so the check is both necessary and sufficient.

Complexity

  • Time — O(n · d(n)) where d(n) is the number of divisors
  • Space — O(n)

Pitfalls

  • The one-liner s in (s + s)[1:-1] is equivalent and O(n) with a linear-time search.
  • Testing non-divisor lengths wastes time and can never match.

Reference solution

Python

def repeatedSubstringPattern(s: str) -> bool:
    n = len(s)
    for length in range(1, n // 2 + 1):
        if n % length != 0:
            continue
        if s[:length] * (n // length) == s:
            return True
    return False

Java

public static boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    for (int len = 1; len <= n / 2; len++) {
        if (n % len != 0) continue;
        String unit = s.substring(0, len);
        boolean ok = true;
        for (int i = len; i < n; i += len) {
            if (!s.substring(i, i + len).equals(unit)) {
                ok = false;
                break;
            }
        }
        if (ok) return true;
    }
    return false;
}

C++

bool repeatedSubstringPattern(string s) {
    int n = (int) s.size();
    for (int len = 1; len <= n / 2; len++) {
        if (n % len != 0) continue;
        bool ok = true;
        for (int i = len; i < n; i++) {
            if (s[i] != s[i - len]) { ok = false; break; }
        }
        if (ok) return true;
    }
    return false;
}

JavaScript

var repeatedSubstringPattern = function(s) {
    const n = s.length;
    for (let len = 1; len <= Math.floor(n / 2); len++) {
        if (n % len !== 0) continue;
        const unit = s.slice(0, len);
        let ok = true;
        for (let i = len; i < n; i += len) {
            if (s.slice(i, i + len) !== unit) { ok = false; break; }
        }
        if (ok) return true;
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings