# LeetCode 249: Group Shifted Strings

## Problem Restatement

We are given an array of lowercase strings.

We need to group strings that belong to the same shifting sequence.

A shift means changing every character to the next character in the alphabet:

```python
a -> b
b -> c
...
z -> a
```

For example:

```python
"abc" -> "bcd" -> "cde" -> ...
```

So these strings belong to the same group:

```python
"abc", "bcd", "xyz"
```

because each one can be shifted into another.

The answer may be returned in any order. The constraints are `1 <= strings.length <= 200`, `1 <= strings[i].length <= 50`, and each string contains lowercase English letters.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of lowercase strings |
| Output | Groups of strings that belong to the same shifting sequence |
| Order | Any group order is accepted |
| Constraint | Each string contains only lowercase English letters |

Example function shape:

```python
def groupStrings(strings: list[str]) -> list[list[str]]:
    ...
```

## Examples

Example 1:

```python
strings = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
```

Valid grouping:

```python
[
    ["acef"],
    ["a", "z"],
    ["abc", "bcd", "xyz"],
    ["az", "ba"],
]
```

Why?

The strings `"abc"`, `"bcd"`, and `"xyz"` share the same shifting pattern.

```python
"abc" -> "bcd" -> ... -> "xyz"
```

The strings `"az"` and `"ba"` also share a shifting sequence:

```python
"az" -> "ba"
```

Single-character strings all belong together because any one letter can shift into any other one-letter string.

```python
"a" -> "b" -> ... -> "z"
```

So `"a"` and `"z"` are grouped together.

## First Thought

We could compare every string with every other string.

For two strings, we can check whether one can be shifted into the other.

But this approach has two problems:

1. It repeats many comparisons.
2. It needs extra logic to merge strings into groups.

A better approach is to compute a canonical key for each string.

Strings with the same key belong to the same group.

## Key Insight

Two strings are in the same shifting sequence when their character differences are the same modulo `26`.

For example:

```python
"abc"
```

has differences:

```python
b - a = 1
c - b = 1
```

And:

```python
"xyz"
```

has differences:

```python
y - x = 1
z - y = 1
```

So both strings have the same pattern:

```python
(1, 1)
```

Another example:

```python
"az"
```

The difference from `a` to `z` is:

```python
25
```

For:

```python
"ba"
```

the difference from `b` to `a` wraps around the alphabet:

```python
(a - b) mod 26 = 25
```

So `"az"` and `"ba"` also share the same key.

## Algorithm

Create a hash map:

```python
key -> list of strings
```

For each string:

1. Compute a key from adjacent character differences.
2. Add the string to the group for that key.
3. Return all hash map values.

For a string `s`, compute its key like this:

```python
diff = (ord(s[i]) - ord(s[i - 1])) % 26
```

Store all differences in a tuple.

For example:

```python
"abc" -> (1, 1)
"bcd" -> (1, 1)
"xyz" -> (1, 1)
"az"  -> (25,)
"ba"  -> (25,)
"a"   -> ()
"z"   -> ()
```

Single-character strings have an empty tuple key, so they group together.

## Correctness

For any string, shifting every character by the same amount does not change the difference between adjacent characters modulo `26`.

Therefore, all strings in the same shifting sequence produce the same key.

Conversely, if two strings produce the same adjacent-difference key, then their letters have the same relative pattern. Starting from the first character of one string, we can shift it to match the first character of the other string. Since all adjacent differences are equal modulo `26`, every following character will also match after the same shift.

Thus, two strings are placed in the same hash map group exactly when they belong to the same shifting sequence.

Since the algorithm computes this key for every string and groups by equal keys, it returns exactly the required groups.

## Complexity

Let `L` be the total number of characters across all strings.

| Metric | Value | Why |
|---|---|---|
| Time | `O(L)` | Each character is processed once while building keys |
| Space | `O(L)` | The hash map stores all strings and their keys |

## Implementation

```python
from collections import defaultdict

class Solution:
    def groupStrings(self, strings: list[str]) -> list[list[str]]:
        groups = defaultdict(list)

        for s in strings:
            key = self._key(s)
            groups[key].append(s)

        return list(groups.values())

    def _key(self, s: str) -> tuple[int, ...]:
        diffs = []

        for i in range(1, len(s)):
            diff = (ord(s[i]) - ord(s[i - 1])) % 26
            diffs.append(diff)

        return tuple(diffs)
```

## Code Explanation

We use a dictionary of lists:

```python
groups = defaultdict(list)
```

Each key represents one shifting sequence.

Each value stores the original strings in that sequence.

For every string:

```python
for s in strings:
```

we compute its key:

```python
key = self._key(s)
```

Then we append the string to the matching group:

```python
groups[key].append(s)
```

The helper function computes adjacent differences:

```python
for i in range(1, len(s)):
    diff = (ord(s[i]) - ord(s[i - 1])) % 26
    diffs.append(diff)
```

The modulo handles wraparound, such as `"az"` and `"ba"`.

Finally, the list of differences is converted to a tuple so it can be used as a dictionary key.

```python
return tuple(diffs)
```

## Testing

Since the answer may be returned in any order, normalize the result before comparing.

```python
def normalize(groups):
    return sorted(sorted(group) for group in groups)

def run_tests():
    s = Solution()

    assert normalize(
        s.groupStrings(["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"])
    ) == normalize([
        ["acef"],
        ["a", "z"],
        ["abc", "bcd", "xyz"],
        ["az", "ba"],
    ])

    assert normalize(s.groupStrings(["a"])) == normalize([
        ["a"],
    ])

    assert normalize(s.groupStrings(["az", "ba"])) == normalize([
        ["az", "ba"],
    ])

    assert normalize(s.groupStrings(["abc", "am"])) == normalize([
        ["abc"],
        ["am"],
    ])

    assert normalize(s.groupStrings(["a", "b", "z"])) == normalize([
        ["a", "b", "z"],
    ])

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Checks all main grouping cases |
| One string | Checks minimum input |
| Wraparound pair | Confirms modulo logic |
| Different lengths and patterns | Confirms unrelated strings stay separate |
| Single-character strings | Confirms all one-letter strings group together |