Loading page…
Practice problem · medium
A search engine indexes product codes that were printed on round stickers. A scanner can start reading a sticker at any letter, so the code abc may be read as abc, bca or cab.
You must count how many different codes the index really holds, when codes that are rotations of each other count as one.
Write count_rotation_groups(words).
words[i] is the i-th code read by a scanner.abc has the rotations abc, bca and cab.Input: words = ["abc", "bca", "cab", "acb"]
Output: 2The trace gives each word a canonical form: the smallest of its rotations in alphabetical order. Rotations of the same word share the form.
| Word | Rotations | Smallest rotation | Set of forms |
|---|---|---|---|
| abc | abc, bca, cab | abc | abc |
| bca | bca, cab, abc | abc | abc |
| cab | cab, abc, bca | abc | abc |
| acb | acb, cba, bac | acb | abc, acb |
The set has two forms, so the output is 2. The word acb is not a rotation of abc, because it reverses the order of b and c.
Input: words = ["a", "a"]
Output: 1The same code twice is one group.
Input: words = ["ab", "abc"]
Output: 2Words of different lengths are never rotations of each other, so the output is 2.
0 ≤ words.length ≤ 100,000 (codes scanned)1 ≤ words[i].length ≤ 20a to z.Comparing every pair of words costs about n × n / 2, which is 5 × 10^9 at n = 100,000. Computing a canonical form costs L × L = 400 steps for a word of at most 20 letters, so the whole job costs about 4 × 10^7. A set then counts the distinct forms.
count_rotation_groups · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.