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:

a -> b
b -> c
...
z -> a

For example:

"abc" -> "bcd" -> "cde" -> ...

So these strings belong to the same group:

"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

Example function shape:

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

Examples

Example 1:

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

Valid grouping:

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

Why?

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

"abc" -> "bcd" -> ... -> "xyz"

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

"az" -> "ba"

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

"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:

"abc"

has differences:

b - a = 1
c - b = 1

And:

"xyz"

has differences:

y - x = 1
z - y = 1

So both strings have the same pattern:

(1, 1)

Another example:

"az"

The difference from a to z is:

25

For:

"ba"

the difference from b to a wraps around the alphabet:

(a - b) mod 26 = 25

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

Algorithm

Create a hash map:

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:

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

Store all differences in a tuple.

For example:

"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.

Implementation

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:

groups = defaultdict(list)

Each key represents one shifting sequence.

Each value stores the original strings in that sequence.

For every string:

for s in strings:

we compute its key:

key = self._key(s)

Then we append the string to the matching group:

groups[key].append(s)

The helper function computes adjacent differences:

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.

return tuple(diffs)

Testing

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

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()