Smallest Repeating Upload
Medium About 30 min Free, no account needed
Find the shortest chunk that reproduces a whole upload, including cases where a long overlap ends mid-copy.
The brief
A sensor sometimes uploads the same short recording several times in a row. Its receiver can store a single chunk plus a repeat count, but it must reproduce the upload exactly. It cannot trim a partial copy or add missing characters.
Implement int Solve(string upload). Return the length of the shortest nonempty prefix whose repeated copies form the entire string. A single copy is allowed. Return 0 for an empty upload.
For "abcabcabc", return 3: three copies of "abc" reproduce the upload. For "abababa", return 7. Although the first six characters repeat, the final "a" leaves a partial copy. For "aaaaaa", return 1.
The string contains only lowercase English letters and has at most 1,000,000 characters. Repeated prefixes can agree almost to the end before a mismatch appears, so repeatedly rebuilding the upload for candidate chunks does too much work.
Starter code
using System;
public class Solution
{
public int Solve(string upload)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- String processing
- Parse, scan and match text character by character with correct edge cases.
Related katas
- Decode String Medium Free Expand k[encoded] patterns, nesting included.
- Count Substring Occurrences Medium Free Count overlapping occurrences by comparing characters, not slicing strings.
- Hex Checksum Medium Free Sum the bytes of a hex string with nibble arithmetic, not substrings.
- Integer to Roman Medium Free Write Roman numerals the way Romans did - greedily.