A cipher drum displays a sequence of n symbols, given as the string word. The drum is serviced in discrete maintenance ticks. On every tick, in order: the operator strips away exactly the first k symbols currently at the front of the drum's sequence, and then stamps k brand-new symbols of their own free choosing onto the back of the drum (any symbols at all, chosen independently on each tick, not required to match anything stripped before). After each tick the sequence's length is unchanged, still exactly n symbols long.
Ticks repeat one after another for as long as needed. The operator wants to know the fewest number of ticks, t (with t >= 1), after which it becomes POSSIBLE for the drum's sequence to read exactly identical to its very first, original sequence again, assuming the operator always stamps whichever symbols best help achieve that outcome as early as possible.
A single line containing the string word, followed by a single space, followed by the integer k.
Print a single integer: the minimum t >= 1 such that the drum's sequence can be made to exactly equal its original starting sequence after t ticks.
Example 1
Input
abacaba 3
Expected
2
Explanation
word = "abacaba" (n=7), k=3. After 1 tick, the front 3 symbols are stripped and 3 new ones are stamped on the back; whatever gets stamped, the only original symbols still physically left untouched form "caba" (the last 4 characters), and that does not match the needed prefix "abac" of the original, so 1 tick cannot work no matter what is stamped. After 2 ticks, a total of 6 original symbols have been stripped, leaving only the single original symbol "a" (the very last character) untouched; that lone leftover does match the required 1-character prefix "a" of the original, so the operator can stamp the remaining 6 positions with "abacab" to exactly restore "abacaba". Hence the answer is 2.
Example 2
Input
abcbabcd 2
Expected
4
Explanation
word = "abcbabcd" (n=8), k=2. Checking t=1, 2, and 3, the untouched trailing remainder of the original word never lines up with the matching prefix of the original word needed to restore it, so no partial restoration is possible before then. Only at t=4, once all 8 original symbols have been stripped across 4 ticks, can the operator simply stamp the entire original word back in piece by piece, exactly reconstructing "abcbabcd". Hence the answer is 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →