mediumStringsPattern: Fast & Slow Pointers
Detecting Cyclic Substring Solution
Problem Statement
Given a string s, determine if there exists a non-empty substring that repeats indefinitely to form the original string, and return the length of the smallest such substring if it exists, otherwise return -1.
Examples
Example 1:
Input:abcabcabcabc
Output:3
Explanation: The smallest repeating substring 'abc' repeats 4 times to form the original string.
Example 2:
Input:abcdabcdabcd
Output:4
Explanation: The smallest repeating substring 'abcd' repeats 3 times to form the original string.
Constraints
- 1 <= s.length <= 10^5
- s consists of only lowercase English letters
- The repeating substring must be non-empty and at least 1 character long
Time: O(n) Space: O(1)
The optimized approach utilizes the fast and slow pointer technique to efficiently check for repeating patterns in the string, resulting in a time complexity of O(n).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.