Two lowercase words belong to the same shift family if one can be turned into the other by shifting every letter forward by the same amount in the alphabet, wrapping from z back to a. For example "abc" and "bcd" (shift 1) and "xyz" (shift 23) are in one family; "az" and "ba" are in another. Given a list words, return the families as a list of lists. Each family must be sorted alphabetically and the families must be ordered by their first word. Duplicates stay in their family.
Examples
Input: words = ["abc", "bcd", "xyz", "az", "ba", "a"]
Output: [["a"], ["abc", "bcd", "xyz"], ["az", "ba"]]
Input: words = ["z", "b", "y"]
Output: [["b", "y", "z"]]
Explanation: any two single letters are a shift of each other.
Constraints
0 <= len(words) <= 5000, each word non-empty and lowercase- Target: O(total characters) time plus the cost of sorting the output.
Goals
- Design a canonical key that is identical for all cyclic shifts of a word
- Group values under a key with a dictionary of lists
- Produce deterministic output by sorting groups and their members