Group shifted strings by their letter-shift pattern

Two strings belong together when shifting every letter of one by the same amount, wrapping from z to a, gives the other. So "abc", "bcd" and "xyz" belong together, and so do "az" and "ba". Group a list of strings by this relation.

Interface

Unless you agree on a different interface with the interviewer, assume:

• group_shifted(strings: list[str]) -> list[list[str]] — one list per group. Inside a group, keep the input order. The groups may be in any order.

Example

group_shifted(["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"])
    ->  [["abc", "bcd", "xyz"], ["acef"], ["az", "ba"], ["a", "z"]]

"az" shifted by 1 gives "ba": a becomes b, and z wraps to a. Every one-letter string is in the same group.

Constraints

• Up to 10^4 strings of lowercase letters, each up to 50 letters long.

Clarifying questions

• Do the strings in one group need the same length? (Yes, a shift keeps the length.)
• Can a string be empty? Can it contain characters other than lowercase letters?
• Does the order of groups or of strings inside a group matter?

What a strong answer covers

• A canonical key per string: the differences between consecutive letters modulo 26, or the string shifted so its first letter becomes a.
• A dictionary from key to group. O(total characters) time and space.
• The wrap-around handled with % 26, and the key turned into a tuple or a delimited string so two different keys cannot look alike.
• Edge cases: empty strings (all in one group), one-letter strings, uppercase or non-letter characters.

Follow-ups

• Allow any printable ASCII, shifting modulo 95.
• Return only the largest group.
• Check whether two given strings belong together, in O(length) and O(1) space.