Abhishek Gupta

Posted on Mar 14

Repeated Substring Pattern in JavaScript — Brute Force Approach Explained

Problem Statement

Given a string s, determine whether it can be constructed by repeating a substring of itself.

Return true if the string can be formed by repeating a substring, otherwise return false.

Example

Input: "abab"
Output: true
Explanation: "ab" repeated 2 times

Input: "abcabcabc"
Output: true
Explanation: "abc" repeated 3 times

Input: "aba"
Output: false

Input: "aaaa"
Output: true
Explanation: "a" repeated 4 times

Understanding the Problem

We need to check if a smaller substring repeats multiple times to form the entire string.

Example:

"abcabcabc"

Possible repeating substring:

"abc"

If we repeat "abc" three times:

"abcabcabc"

This matches the original string, so the answer is true.

But consider:

"aba"

There is no substring that can repeat to form "aba", so the answer is false.

Brute Force Approach

The simplest way to solve this problem is to try every possible substring and check if repeating it forms the original string.

Important observation:

The repeating substring length must divide the length of the string.

Example:

String = "abab"
Length = 4

Possible substring lengths:

1
2

Now test them.

Substring "a":

"a".repeat(4) → "aaaa" ❌

Substring "ab":

"ab".repeat(2) → "abab" ✅

So "ab" is the repeating substring.

Algorithm

Get the length of the string.
Iterate through all possible substring lengths from 1 to length / 2.
If the string length is divisible by the substring length:

Extract the substring.
Repeat it enough times to match the original length.
Compare it with the original string.
1. If a match is found → return true.
2. Otherwise return false.

JavaScript Implementation

var repeatedSubstringPattern = function(s) {

    let len = s.length;

    for (let i = 1; i <= len / 2; i++) {

        if (len % i === 0) {

            let sub = s.slice(0, i);

            if (sub.repeat(len / i) === s) {
                return true;
            }

        }

    }

    return false;
};

Testing the Solution

console.log(repeatedSubstringPattern("abcabcabcabc")); 
// true

console.log(repeatedSubstringPattern("aba")); 
// false

console.log(repeatedSubstringPattern("abab")); 
// true

console.log(repeatedSubstringPattern("aaaa")); 
// true

Dry Run Example

Let’s test the string:

"ababab"

Length:

Possible substring lengths:

1, 2, 3

Check each one.