Galactic Transmission Decoding 2 — Problem Statement & Solution Guide
Problem Description
A deep-space probe transmits a compressed binary signal to Earth. The transmission protocol dictates that the raw data is constructed by repeating a single, contiguous binary substring (the 'key') an integer number of times. Due to signal degradation, the receiver must determine the minimal length of this key to decompress the message efficiently.
Given a string s consisting solely of characters '0' and '1', identify the length of the shortest prefix p such that s can be formed by concatenating p with itself one or more times. If the string cannot be decomposed into such a repeated pattern (i.e., the string is primitive), return -1.
For instance, if s is "010101", the shortest repeating unit is "01" (length 2), because "01" repeated 3 times yields the original string. If s is "0110", no proper prefix repeats to form the whole string, so the result is -1.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Transmission Decoding 2"
WHY DOES IT MATTER?
Detecting the minimal period is a classic string periodicity problem that appears in compression, pattern matching, and DNA sequence analysis. Mastery of this pattern demonstrates a candidate's ability to translate combinatorial string properties into linear‑time algorithms.
OPTIMIZATION CHALLENGE
The key insight is that the longest border of the whole string encodes the maximal overlap between prefix and suffix, and subtracting its length from the total yields the smallest possible period. This eliminates the need to test every divisor of n.
REAL-WORLD CONNECTION
In distributed log aggregation, a log entry may be a repeated heartbeat pattern; identifying the smallest repeating unit allows efficient storage and deduplication, similar to how network protocols compress repeated frames.
When coding, compute the prefix array once, store it in a simple int[]; avoid recomputing pi for substrings. After the array is built, the final answer is a one‑liner: int period = n % (n - pi[n-1]) == 0 ? n - pi[n-1] : n;
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem asks for the smallest building block (key) whose repeated concatenation yields the original binary string. This is essentially the computation of the string's minimal period. A naive scan of all possible prefix lengths leads to O(n^2) time because each candidate must be verified by comparing up to n characters. For large inputs (n up to 10^6 or more) this quickly becomes infeasible. The optimal paradigm leverages the failure function of the Knuth-Morris-Pratt (KMP) algorithm (or equivalently the Z‑function) to capture the longest proper prefix that is also a suffix for every prefix of the string in linear time. The value pi[n‑1] (the last entry of the prefix table) tells us the length of the longest border of the whole string. If we denote L = n - pi[n‑1], then L is the candidate period; the string is composed of repetitions of a substring of length L exactly when n % L == 0. This reduces the problem to a single pass O(n) preprocessing and a constant‑time check.
Why this works stems from the combinatorial property of borders: any period must align with a border, and the longest border gives the greatest possible reduction. By subtracting the border length from the total length we obtain the smallest shift that could repeat. If the total length is not an integer multiple of this shift, the string has no smaller period and the answer defaults to n. Thus the KMP prefix function provides both correctness and optimality, delivering O(n) time and O(n) auxiliary space.
Alternative linear‑time approaches include using the Z‑algorithm to find the smallest index i where Z[i] == n - i and i divides n, or employing string hashing with binary search, but KMP remains the most straightforward and deterministic method for this exact problem.
Interview Questions on This Problem
Q1How would you find the length of the smallest repeating substring in a binary string in O(n) time?
Compute the KMP prefix function for the string. Let n be the length and p = pi[n-1]. The candidate period is L = n - p. If n % L == 0, L is the answer; otherwise the answer is n.
Q2Can you solve the same problem using the Z‑function? Explain the steps.
Build the Z‑array in O(n). Scan i from 1 to n-1; if Z[i] == n - i and i divides n, then i is the minimal period. If no such i exists, the period is n.
Q3Why does checking n % (n - pi[n-1]) guarantee that the whole string is composed of repetitions of the prefix of length (n - pi[n-1])?
pi[n-1] is the length of the longest border, meaning the prefix of length pi[n-1] equals the suffix of the same length. Subtracting this border from n yields the smallest shift that aligns the string with itself. If n is a multiple of that shift, the prefix repeats perfectly to fill the string; otherwise a smaller shift cannot exist.
Examples
Input
s = "11001100"
Output
4
Explanation: The string length is 8. We check divisors of 8: 1, 2, 4, 8. 1. Length 1: Prefix "1". Repeating "1" 8 times gives "11111111" != "11001100". 2. Length 2: Prefix "11". Repeating "11" 4 times gives "11111111" != "11001100". 3. Length 4: Prefix "1100". Repeating "1100" 2 times gives "11001100" == s. Thus, the shortest pattern length is 4.
Input
s = "01010101"
Output
2
Explanation: The string length is 8. We check divisors of 8: 1, 2, 4, 8. 1. Length 1: Prefix "0". Repeating "0" 8 times gives "00000000" != "01010101". 2. Length 2: Prefix "01". Repeating "01" 4 times gives "01010101" == s. Thus, the shortest pattern length is 2.
Input
s = "10110"
Output
-1
Explanation: The string length is 5. Since 5 is a prime number, the only divisors are 1 and 5. 1. Length 1: Prefix "1". Repeating "1" 5 times gives "11111" != "10110". 2. Length 5: This is the whole string, which implies no repetition (or repetition count 1, which is trivial and usually excluded in 'shortest repeated pattern' contexts where we look for a proper substring, but even if allowed, the problem asks for the pattern that *makes up* the string via repetition. Typically, if no proper prefix works, it's -1). Since no proper prefix repeats to form the string, return -1.
Input
s = "000000"
Output
1
Explanation: The string length is 6. We check divisors of 6: 1, 2, 3, 6. 1. Length 1: Prefix "0". Repeating "0" 6 times gives "000000" == s. Thus, the shortest pattern length is 1.
Constraints
- 1 <= s.length <= 10^5
- s consists of characters '0' and '1' only
Optimal Approach & Strategy
Build the KMP prefix table in O(n) and use the last entry to compute the minimal period with a single modulo check.
Brute Force Approach
Try every prefix length from 1 to n, and for each, verify by scanning the whole string whether it repeats perfectly.
Verified Code Solutions
function solution(s) {
let n = s.length;
for (let len = 1; len <= n / 2; len++) {
if (n % len === 0) {
let pattern = s.substring(0, len);
let repeated = s.substring(0, len * (n / len));
if (repeated === s) {
return len;
}
}
}
return -1;
}class Solution {
public:
int solution(string s) {
int n = s.length();
for (int len = 1; len <= n / 2; len++) {
if (n % len == 0) {
string pattern = s.substr(0, len);
string repeated = s.substr(0, len * (n / len));
if (repeated == s) {
return len;
}
}
}
return -1;
}
};class Solution {
public int solution(String s) {
int n = s.length();
for (int len = 1; len <= n / 2; len++) {
if (n % len == 0) {
String pattern = s.substring(0, len);
String repeated = s.substring(0, len * (n / len));
if (repeated.equals(s)) {
return len;
}
}
}
return -1;
}
}def solution(s):
n = len(s)
for len_ in range(1, n // 2 + 1):
if n % len_ == 0:
pattern = s[:len_]
repeated = s[:len_ * (n // len_)]
if repeated == s:
return len_
return -1function solution(s) {
let n = s.length;
for (let len = 1; len <= n / 2; len++) {
if (n % len === 0) {
let pattern = s.substring(0, len);
let repeated = s.substring(0, len * (n / len));
if (repeated === s) {
return len;
}
}
}
return -1;
}Asked in Top Tech Interviews
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.