Two words share the same structural pattern if, reading left to right and replacing each character by the index (starting at 0) at which its letter first appeared within that word, the resulting sequences of indices are identical. For example, abba becomes 0 1 1 0, and xyyx also becomes 0 1 1 0 — so abba and xyyx share the same pattern even though they use different letters. aabb becomes 0 0 1 1, a different pattern.
Given n lowercase words, group them by this structural-pattern equivalence and print the number of distinct groups.
Line 1: an integer n.
Line 2: n space-separated lowercase words.
A single integer: the number of distinct structural-pattern groups among the n words.
Example 1
Input
4 abba xyyx aabb ab
Expected
3
Explanation
abba and xyyx both follow the pattern 0 1 1 0, so they form one group. aabb (pattern 0 0 1 1) and ab (pattern 0 1, a different length) each form their own group. Total: 3 groups.
Example 2
Input
3 aaa aaa bbb
Expected
1
Explanation
All three words follow the pattern 0 0 0 (every character repeats the first), regardless of which letter is used, so all three belong to the same 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 →