226. Group Shifted Strings
Shifting a string nudges every character forward to the next letter of the alphabet, with z wrapping around to a: shifting "abc" gives "bcd", and shifting "az" gives "ba". Two strings belong to the same shifting family when applying the shift zero or more times to one of them produces the other.
You are given a list of lowercase strings strings. Bundle them into their shifting families and return the families as a list of groups.
So that the answer is unique: inside each group keep the strings in their original input order (duplicates stay as separate entries), and order the groups by where each family's first member appears in the input.
Example 1:
Input: strings = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
Output: [["abc", "bcd", "xyz"], ["acef"], ["az", "ba"], ["a", "z"]]
Explanation: Shifting abc once gives bcd, and 23 more shifts reach xyz, so those three share a family. az shifts to ba (the z wraps to a). Every single-letter string can shift into any other, so a and z sit together. acef lines up with nothing else.
Example 2:
Input: strings = ["mnop", "qrst", "abcd", "dcba"]
Output: [["mnop", "qrst", "abcd"], ["dcba"]]
Explanation: mnop shifted 4 times is qrst, and abcd shifted 12 times is mnop, so all three share one family. dcba runs backwards — its letter-to-letter gaps differ — so it stands alone.
Constraints:
- 1 ≤ n ≤ 200
- 1 ≤ strings[i].length ≤ 50
- strings[i] consists of lowercase English letters only.
- The input may contain duplicates; every occurrence is kept.
Hints:
Members of one family must have the same length, and shifting never changes the *gap* between two positions: if t is a shift of s, then (t[i] − t[0]) mod 26 equals (s[i] − s[0]) mod 26 for every i. Watch the mod — the wrap from z to a makes raw differences go negative.
Turn that invariant into a canonical fingerprint: slide each string so its first character becomes 'a' (subtract s[0] from every character, mod 26), or equivalently record the tuple of offsets from the first character. Two strings share a family exactly when they share a fingerprint.
One pass with a hash map from fingerprint → group index collects the families, and appending a fresh group whenever a new fingerprint shows up produces the required first-appearance ordering automatically.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: strings = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
Expected output: [["abc", "bcd", "xyz"], ["acef"], ["az", "ba"], ["a", "z"]]