Even–Odd Shuffle Classes

Medium

You get a list words of equal-length strings made of lowercase English letters. In one move you may swap two characters of a string that sit at positions of the same parity: both even or both odd (0-based). You can make as many moves as you like. Call two strings related if one can be turned into the other with such moves. Being related splits the list into classes: strings within a class are related, and strings from different classes are not. Return the number of classes.

Example 1

words=["stop", "pots", "tops", "opts"] → 3

The even positions of "stop" hold s, o and the odd ones hold t, p. In "pots" the even positions hold p, t, a different set. The classes are {stop}, {pots, tops}, {opts}: "pots" turns into "tops" by swapping p and t at positions 0 and 2.

Example 2

words=["ab", "ba", "ab"] → 2

In a two-letter word the letters sit at positions of different parity, so they cannot be swapped. The classes are {ab, ab} and {ba}.

Example 3

words=["abcde", "edcba", "cbade"] → 1

Constraints

1 ≤ len(words) ≤ 10⁴
1 ≤ len(words[i]) ≤ 20
All strings have the same length
Strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String Sorting