A lock factory stamps codes that are all rearrangements of the same letters, so every string in codes is an anagram of every other one (same length, same letter counts). Two codes are neighbours if they are identical, or if swapping the characters at exactly two positions of one code produces the other.
A cluster is a maximal set of codes where any two are joined by a chain of neighbours (the codes need not be neighbours directly). Return the number of clusters. Duplicate strings in the list are separate entries but always share a cluster.
Examples
Input: codes = ["abcd", "bacd", "badc", "dcba"]
Output: 2
Explanation: "abcd" - "bacd" (swap positions 0, 1) - "badc" (swap 2, 3); "dcba" differs from each of them in four positions.
Input: codes = ["xyz", "xyz"]
Output: 1
Input: codes = ["abc", "acb", "bca"]
Output: 1
Explanation: "acb" and "bca" differ only at positions 0 and 2.
Constraints
0 <= len(codes) <= 400,1 <= len(codes[i]) <= 20, lowercase letters, all codes are anagrams of each other- Target: O(n^2 * L) time, where L is the code length.
Goals
- Test the one-swap relation with a single pass over two strings
- Group items through a relation that is not itself transitive