Repeated Substring Pattern

easy string string matching

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.

Inputs = "abcabcabc"

Outputtrue

"abc" repeated three times forms the input.

def repeated_substring_pattern(s):
    n = len(s)
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            if s[:d] * (n // d) == s:
                return True
    return False

function repeatedSubstringPattern(s) {
  const n = s.length;
  for (let d = 1; d <= n / 2; d++) {
    if (n % d !== 0) continue;
    if (s.slice(0, d).repeat(n / d) === s) return true;
  }
  return false;
}

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int d = 1; d <= n / 2; d++) {
            if (n % d != 0) continue;
            String p = s.substring(0, d);
            StringBuilder sb = new StringBuilder();
            for (int k = 0; k < n / d; k++) sb.append(p);
            if (sb.toString().equals(s)) return true;
        }
        return false;
    }
}

bool repeatedSubstringPattern(string s) {
    int n = s.size();
    for (int d = 1; d <= n / 2; d++) {
        if (n % d != 0) continue;
        string p = s.substr(0, d);
        string built;
        for (int k = 0; k < n / d; k++) built += p;
        if (built == s) return true;
    }
    return false;
}

Explanation

If a string is built by repeating some block, the block's length must evenly divide the whole length n. So we only need to test prefix lengths d that are divisors of n, and the candidate block is always the prefix s[:d].

We loop d from 1 up to n // 2 (a repeating block can be at most half the string, since it must appear at least twice). We skip any d where n % d != 0, because a block that does not divide n can never tile it exactly.

For a valid divisor, we build the prefix repeated the right number of times, s[:d] * (n // d), and compare it to s. If it matches, the string is periodic and we return True. If no divisor works, we return False.

Example: s = "abcabcabc" has length 9. d = 1 ("a"*9) and d = 2 (not a divisor) fail, but d = 3 gives "abc" * 3 = "abcabcabc", which equals s, so the answer is true.

Time: O(n · √n) Space: O(n)