Group Lowercase Strings into Families Related by a Uniform Letter Shift
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Shifting a string of lowercase letters moves every character forward by the same number of places in the alphabet, wrapping from `z` back to `a`. Shifting `"abc"` by 1 gives `"bcd"`, and shifting `"az"` by 1 gives `"ba"`. Two strings belong to the same **shift family** when one of them becomes the other after a single shift by some amount from 0 to 25.
Given a list of strings, split it into shift families.
### Function Signature
```python
def group_shift_families(strings: List[str]) -> List[List[str]]:
```
### Rules
- A shift moves every character of the string by the same amount, modulo 26.
- Strings of different lengths are never in the same family.
- Every input element appears exactly once in the output. Duplicate strings are separate elements and land in the same family.
- Inside a family, strings appear in their input order.
- Families are ordered by the input index of their first member.
### Constraints
- `1 <= len(strings) <= 10^4`
- `1 <= len(strings[i]) <= 50`
- Every string contains only the lowercase English letters `a` to `z`.
### Examples
**Example 1**
```text
Input: strings = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
Output: [["abc", "bcd", "xyz"], ["acef"], ["az", "ba"], ["a", "z"]]
```
Shifting `"abc"` by 1 gives `"bcd"` and by 23 gives `"xyz"`. No other string has length 4, so `"acef"` is alone. Shifting `"az"` by 1 gives `"ba"`. Any two one-letter strings are shifts of each other. The families start at input indices 0, 2, 4 and 6.
**Example 2**
```text
Input: strings = ["ab", "ab", "yz", "ac"]
Output: [["ab", "ab", "yz"], ["ac"]]
```
Both copies of `"ab"` are kept, and `"yz"` is `"ab"` shifted by 24.
**Example 3**
```text
Input: strings = ["a"]
Output: [["a"]]
```
Overview: A string-grouping coding problem: split a list of lowercase strings into families whose members turn into one another when every letter is shifted by the same amount with wraparound. It tests string normalization, modular arithmetic on letters and grouping with a deterministic output order.
Read the full Meta Software Engineer interview experience this question came from