Repeated Substring Pattern

Repeated Substring Pattern

What is this problem about?

The Repeated Substring Pattern interview question asks you to determine whether a given string can be constructed by repeating a smaller substring multiple times. For example, "abababab" is built by repeating "ab" four times, so the answer is true. But "abcab" cannot be expressed as a repeated pattern, so the answer is false. This is a string matching problem with an elegant mathematical trick.

Why is this asked in interviews?

This problem is asked at Microsoft, Meta, Amazon, Google, and Bloomberg because it tests string pattern recognition and knowledge of the KMP (Knuth-Morris-Pratt) failure function — a fundamental string algorithm used in text search engines, bioinformatics, and data compression. It also has a clever two-line trick using string doubling and containment, which rewards candidates who think creatively beyond brute force.

Algorithmic pattern used

Two main patterns apply. The first is brute-force enumeration: try every possible prefix length that divides the string length, construct the repeated version, and check equality. The second is the string doubling trick: concatenate the string with itself to form s + s, then check if the original string s appears in the middle portion (excluding the first and last characters). If s appears in (s+s)[1:-1], then s has a repeated substring pattern. The KMP failure function can also confirm this in O(n) time.

Example explanation

String: "xyzxyz".

• Try substring "xyz" (length 3, divides 6): repeat twice → "xyzxyz" matches original. Return true.

String doubling trick: "xyzxyz" + "xyzxyz" = "xyzxyzxyzxyz". Trim first and last char: "xyzxyzxyzxy". Does "xyzxyz" appear here? Yes, at index 3. Return true.

String: "abcde": No prefix whose repetition reconstructs the string exists. Return false.

Common mistakes candidates make

• Only checking substrings whose length divides the original length — this is correct, but candidates sometimes forget to enforce divisibility.
• Using O(n^2) substring generation without realizing the doubling trick gives an O(n) solution.
• Forgetting to exclude the first and last characters when applying the doubling check.
• Testing prefix length equal to the full string length, which trivially matches but is an invalid single-repeat.

Interview preparation tip

For the Repeated Substring Pattern coding problem, the string matching interview pattern rewards knowing the doubling trick: create t = s + s, then check s in t[1:-1]. Practice explaining why this works: if s has a repeated substring, the double string contains a shifted copy of s at a non-zero, non-n offset. Interviewers at Microsoft and Google appreciate when you mention both the brute-force and the O(n) approach with a clear justification for the doubling technique.