Detecting Cyclic Substring — Problem Statement & Solution Guide

StringsMediumFast & Slow Pointers

TimeO(n)

SpaceO(n)

Problem Description

Given a string s consisting of lowercase English letters, determine the length of the smallest non-empty substring that, when repeated consecutively, reconstructs the entire string s. If no such substring exists, return -1.

A substring is considered cyclic if it can be tiled to form the original string without any gaps or overlaps. For example, if s is "abcabc", the substring "abc" is cyclic because "abc" + "abc" equals s. The goal is to find the minimum length of such a cyclic substring.

Return an integer representing the length of the smallest cyclic substring, or -1 if the string cannot be formed by repeating any shorter substring.

DSA Pattern Breakdown

"Detecting Cyclic Substring"

medium

WHY DOES IT MATTER?

Detecting the minimal period of a string is a classic pattern that appears in compression, pattern matching, and periodicity analysis. Mastering this pattern teaches you how to translate a seemingly combinatorial problem into a linear‑time string algorithm, a skill that recurs in many interview challenges.

OPTIMIZATION CHALLENGE

The key insight is that the prefix function captures the longest border of every prefix, and the border length of the whole string directly reveals the smallest period. By avoiding explicit substring comparisons for each divisor, you collapse O(n^2) work into a single linear pass.

REAL-WORLD CONNECTION

In distributed log aggregation, a repeating log pattern can be compacted by storing the base pattern and a repeat count, similar to how network protocols compress repetitive payloads using run‑length encoding. Recognizing the base pattern reduces storage and bandwidth, mirroring the cyclic substring detection.

During an interview, compute the prefix array first, then derive the answer with a one‑liner: if n % (n - pi[n-1]) == 0 return n - pi[n-1] else return -1. This shows you understand both the algorithm and its concise application.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem asks for the length of the smallest non‑empty substring that can be tiled to reconstruct the whole string. This is equivalent to finding the minimal period of the string. A string s of length n has period p if for every i (0 ≤ i < n‑p) s[i] == s[i+p]; the smallest such p is the answer. A naive check of every possible divisor of n and comparing slices leads to O(n^2) time, which fails for large inputs (n up to 10^5 or more). The optimal paradigm leverages the failure function (also called prefix function) from the Knuth‑Morris‑Pratt (KMP) algorithm. The prefix function π[i] stores the length of the longest proper prefix of s[0..i] that is also a suffix. For the whole string, let l = π[n‑1]; the length of the smallest repeating unit is n - l if n % (n - l) == 0, otherwise no such unit exists. This reduces the problem to a single linear scan, achieving O(n) time and O(n) auxiliary space (or O(1) extra space if the prefix array is computed in‑place).

Interview Questions on This Problem

Q1How would you find the smallest repeating substring in a string using only O(1) extra space?

Compute the KMP prefix function on the fly using two pointers and a temporary variable to store the current length of the longest border, updating it as you iterate; you only need the last value π[n‑1] to decide the period, so you can discard earlier entries, achieving O(1) extra space.

Q2Why does checking only the divisors of the string length suffice when searching for a cyclic substring?

A substring that tiles the whole string must repeat an integer number of times, so its length must divide the total length n. If a length p does not divide n, the repeats would either fall short or overshoot, making a perfect tiling impossible.

Q3Can you adapt the solution to work for strings with Unicode characters or case‑insensitive matching?

Yes. The algorithm operates on character equality, so you can preprocess the string to a normalized form (e.g., lower‑casing and Unicode normalization) before building the prefix function; the complexity remains linear because the preprocessing is also O(n).

Examples

Example 1

Input

"ababab"

Output

Explanation: The string "ababab" can be formed by repeating "ab" three times. The length of "ab" is 2. No smaller non-empty substring (like "a" or "b") can form the entire string. Thus, the answer is 2.

Example 2

Input

"abcabcabc"

Output

Explanation: The string "abcabcabc" is composed of three repetitions of "abc". The length of "abc" is 3. Checking divisors of 9 (1, 3, 9), only 3 yields a valid repeating unit. Thus, the answer is 3.

Example 3

Input

"hello"

Output

-1

Explanation: The string "hello" has length 5, which is prime. The only possible divisors are 1 and 5. Repeating "h" five times gives "hhhhh", which does not match "hello". Therefore, no cyclic substring exists, and the answer is -1.

Example 4

Input

"aaaaaa"

Output

Explanation: The string "aaaaaa" can be formed by repeating "a" six times. The length of "a" is 1. This is the smallest possible non-empty substring. Thus, the answer is 1.

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters only

Optimal Approach & Strategy

Build the KMP prefix function in O(n) time, derive the candidate period from the last prefix value, and verify divisibility in O(1).

Brute Force Approach

Try every possible substring length that divides the string length and compare each repeated block to the original; this costs O(n^2) in the worst case.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(s) {
   let n = s.length;
   for (let len = 1; len <= n; len++) {
       if (n % len === 0) {
           let substr = s.slice(0, len);
           if (s === substr.repeat(n / len)) {
               return len;
           }
       }
   }
   return -1;
}

class Solution {
   public:
       int solution(string s) {
           int n = s.length();
           for (int len = 1; len <= n; len++) {
               if (n % len == 0) {
                   string substr = s.substr(0, len);
                   if (s == substr.repeat(n / len)) {
                       return len;
                   }
               }
           }
           return -1;
       }
   };

class Solution {
   public int solution(String s) {
       int n = s.length();
       for (int len = 1; len <= n; len++) {
           if (n % len == 0) {
               String substr = s.substring(0, len);
               if (s.equals(substr.repeat(n / len))) {
                   return len;
               }
           }
       }
       return -1;
   }
}

def solution(s):
   n = len(s)
   for len in range(1, n + 1):
       if n % len == 0:
           substr = s[:len]
           if s == substr * (n // len):
               return len
   return -1

function solution(s) {
   let n = s.length;
   for (let len = 1; len <= n; len++) {
       if (n % len === 0) {
           let substr = s.slice(0, len);
           if (s === substr.repeat(n / len)) {
               return len;
           }
       }
   }
   return -1;
}

Asked in Top Tech Interviews

Adobe

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Detecting Cyclic Substring Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Detecting Cyclic Substring — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor