Small case is 10k: n^2 is not enough

consider if an answer exists, then we can break down the whole string into product of

1 * i * 1 * j * 1  * k * 1

Reductio ad absurdum: consider the shortest prefix s.t. product is i, i.e, the “padding”, then the product must be of form

prefix * 1 * j * 1 * k * 1

i.e., when a solution exists, we can break it down in a way that the shortest prefix that forms i is part of the solution

by similar argument, we can find the shortest prefix that forms j, after the shortest prefix that forms i.

Since the group has 4 elements, the cycle length has max 4,i.e.,

(word repeating 1 to 4 times, depending on the product of word) * prefix = prefix

This means if a prefix is a repitition of words more than 4 tims, it can not be the shorteset prefix

i.e., we can find prefix for i and j within first 8 words => we reduced it to smaller case!

Note that with i, j , we can infer if k exists by “dividing” the product of word* by i*j, since divide/product is one-to-one mapping, we can infer the suffix

Because the whole word is repeated, we can calc the product in log(n)