A vintage music-box restorer is cataloguing a crate of cylinder engravings. Each cylinder's engraving is written down as a string of lowercase letters, one letter per pin position. Two cylinders play the same tune in a different key if there is some fixed shift amount (the same shift applied to every pin, wrapping from z back to a) that turns every letter of the first cylinder's engraving into the corresponding letter of the second cylinder's engraving, position for position. Shifting by 0 leaves an engraving unchanged, so two identical engravings always count as the same tune, and only engravings of equal length can ever match.
Given the engravings of all cylinders in the crate, count how many unordered pairs of distinct cylinders play the same tune in some key.
Line 1: a single integer n — the number of cylinders.
Line 2: n space-separated strings — the engravings, in order.
A single integer — the number of pairs of cylinders that play the same tune in some key.
a-z).Example 1
Input
4 abc bcd xyz cde
Expected
6
Explanation
The four engravings 'abc', 'bcd', 'xyz', 'cde' all have length 3. Looking at how far each later letter is past the first letter: 'abc' gives offsets (0,1,2); 'bcd' gives (0,1,2); 'xyz' gives (0,1,2); 'cde' gives (0,1,2). All four share the identical offset pattern, so shifting any one by the right fixed amount reproduces any other. Every one of the C(4,2)=6 pairs matches, so the answer is 6.
Example 2
Input
4 ab ba xy cba
Expected
1
Explanation
'ab' has offset pattern (0,1) from its first letter. 'ba' has offset pattern (0,25), since going forward from 'b' to 'a' wraps around 25 steps. 'xy' has offset pattern (0,1), matching 'ab'. 'cba' has length 3, so it cannot match any length-2 engraving. Only the pair ('ab','xy') matches, so the answer is 1.
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 →