A jewelry-cataloging tool stores n bead-pattern strings, each of the same length. Two bead patterns belong to the same necklace group if one can be obtained from the other by rotating it cyclically (moving characters from the front to the back, e.g. abcd → bcda → cdab → dabc are all rotations of one another and thus the same necklace group).
Count the number of distinct necklace groups among the n given patterns.
Line 1: an integer n.
Lines 2 to n+1: one bead-pattern string per line. All n strings have the same length.
A single integer: the number of distinct necklace (rotation-equivalence) groups.
n patterns have the same length.Example 1
Input
4 abcd bcda dcba cdab
Expected
2
Explanation
abcd, bcda, and cdab are all rotations of one another, forming one group. dcba is not a rotation of abcd (its rotations are abcd, bcda, cdab, dabc — dcba is not among them), so it forms its own group. Total: 2 groups.
Example 2
Input
3 aab aba baa
Expected
1
Explanation
aab, aba, and baa are all cyclic rotations of each other, so they form a single group.
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 →