mediumStringsPattern: Fast/Slow Pointers
Galactic Transmission Decoding Solution
Problem Statement
In a deep space transmission, messages are encoded by repeating a pattern of binary digits. Given a string of binary digits, write a function to find the length of the shortest repeated pattern that makes up the entire string. A repeated pattern is a sequence of binary digits that can be repeated to form the original string. If no such pattern exists, return -1.
Examples
Example 1:
Input:101010
Output:2
Explanation: The pattern '10' can be repeated to form the string.
Example 2:
Input:111111
Output:1
Explanation: The pattern '1' can be repeated to form the string.
Example 3:
Input:12345
Output:-1
Explanation: There is no repeated pattern that makes up the entire string.
Constraints
- 1 <= length of string <= 1000
- The string consists only of binary digits (0s and 1s).
- The function should have a time complexity of O(n^2) or better.
Time: O(n) Space: O(1)
The optimized approach involves checking all factors of the string length as possible pattern lengths, resulting in a time complexity of O(n). This is because if a string can be formed by repeating a pattern, then the length of the pattern must be a factor of the length of the string.
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.