>>109316686
>isn't this really easy
>just normalize each string by taking e.g. the lexicographically smallest transformed version
No
the question is really long and confusing but what it boils down to is classifying each string based on the characters of their even and odd indices.
So two strings belong into the same group if you can make all of their odd indices and all of their even indices the same by rotation.
"abc" goes into the same group as "cba"
"abc" -> "ac" (even) + "b" (odd)
"cba" -> "ca" -> rotate into "ac" (even) + "b" (odd)
and you do this for every string in the input.
So the pseudo code goes like:
groups = [String: Int]
for string in words {
E = (extract even indices)
O = (extract odd indices)
(lexicographically rotate E and O)
groups[E_O] += 1
}
return groups.count
The issue is on the lexicographic rotation. The input size is 100,000 words and each word can be up to 500,000 characters long. trying out each combination of rotations in each word gives you n^2 complexity which TLEs after 640/693 testcases.
To bring the final operation down to O(n) time you need "Booth's Algorithm for Lexicographically minimal string rotation" (lmao)
I didn't know the algorithm so I wasn't able to solve the question.
