LeetCode 249: Group Shifted Strings Solution in Python – A Step-by-Step Guide

What Is LeetCode 249: Group Shifted Strings?

In LeetCode 249: Group Shifted Strings, you’re given a list of strings, and your task is to group them into lists where each group contains strings that are "shifted" versions of one another. A string is a shifted version if each character can be transformed into the next by adding the same number (modulo 26) to its position in the alphabet. This problem is a creative twist on string manipulation, related to LeetCode 242: Valid Anagram, but focusing on shifts rather than character counts.

Problem Statement

• Input: A list of strings strings containing lowercase letters.
• Output: A list of lists, where each sublist contains strings that are shift-equivalent.
• Rules: Shifting wraps around (e.g., 'z' + 1 = 'a'); all strings in a group must be the same length.

Constraints

• List length: 1 to 200.
• String length: 0 to 100.
• Characters: Lowercase English letters only.

Examples

• Input: strings = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
• Output: [["abc", "bcd", "xyz"], ["acef"], ["az", "ba"], ["a"], ["z"]]
• Input: strings = ["a"]
• Output: [["a"]]

Understanding the Problem: Grouping by Shifts

To solve LeetCode 249: Group Shifted Strings in Python, we need to group strings that can be aligned by shifting their letters by a consistent amount. For example, "abc" shifts to "bcd" (each letter +1), and "bcd" shifts to "cde" (another +1). The key is to identify a "shift pattern" that’s unique to each group, despite the actual letters. We’ll use two methods: 1. Best Solution (Hash Map with Normalization): O(n * k) time—fast and clever. 2. Alternative Solution (Brute Force Comparison): O(n² * k) time—simple but slow.

Let’s dive into the best solution with extra detail for beginners.

Best Solution: Hash Map with Shift Normalization

Why This Is the Best Solution

The hash map with shift normalization approach is the top pick for LeetCode 249 because it runs in O(n * k) time (where n is the number of strings and k is the max string length) by converting each string into a unique "shift key" and grouping them efficiently. It uses minimal extra space and scales well, making it the go-to solution.

How It Works

Think of this solution as giving each string a secret code based on how its letters shift relative to each other, then putting all strings with the same code in a box together. The trick is to create a code that stays the same no matter where the string starts in the alphabet. Here’s how it works, step-by-step, explained simply:

• Shift Pattern: For "abc" to "bcd", each letter shifts by 1 ('a'→'b', 'b'→'c', 'c'→'d'). The differences between consecutive letters tell us the pattern.
• Normalization:
• Take each string and calculate the difference between adjacent characters.
• Adjust for wrapping (e.g., 'z' to 'a' is 1, not -25) by adding 26 and taking modulo 26.
• For "abc": 'b'-'a' = 1, 'c'-'b' = 1 → pattern "1,1".
• For "bcd": 'c'-'b' = 1, 'd'-'c' = 1 → same "1,1".
• Hash Map:
• Use the pattern (e.g., "1,1") as a key in a dictionary.
• Store all strings with that pattern in a list under that key.
• Handle Single Letters: For "a" or "z", no differences exist, so use an empty pattern.
• Group: Each dictionary value is a group of shift-equivalent strings.

It’s like sorting friendship bracelets by their bead patterns—same pattern, same group!

Step-by-Step Example

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

• Process Each String:
• "abc": Differences = (b-a, c-b) = (1, 1) → key "1,1".
• "bcd": (c-b, d-c) = (1, 1) → key "1,1".
• "acef": (c-a, e-c, f-e) = (2, 2, 1) → key "2,2,1".
• "xyz": (y-x, z-y) = (1, 1) → key "1,1".
• "az": (z-a) = (25) → key "25".
• "ba": (a-b) = (-1 + 26 = 25) → key "25".
• "a": No differences → key "".
• "z": No differences → key "".
• Group in Hash Map:
• "1,1": ["abc", "bcd", "xyz"].
• "2,2,1": ["acef"].
• "25": ["az", "ba"].
• "": ["a", "z"].
• Result: [["abc", "bcd", "xyz"], ["acef"], ["az", "ba"], ["a", "z"]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        # Step 1: Set up our grouping box (dictionary)
        shift_groups = {}

        # Step 2: Process each string
        for s in strings:
            # Step 3: Create the shift pattern (key)
            if len(s) == 1:
                key = ""  # Single letters have no differences
            else:
                # Calculate differences between consecutive letters
                diffs = []
                for i in range(1, len(s)):
                    # Get ASCII difference, adjust for wrap-around
                    diff = (ord(s[i]) - ord(s[i-1])) % 26
                    diffs.append(str(diff))
                # Join differences into a string key
                key = ",".join(diffs)

            # Step 4: Add string to its group
            if key in shift_groups:
                shift_groups[key].append(s)
            else:
                shift_groups[key] = [s]

        # Step 5: Return all groups
        return list(shift_groups.values())

• Time Complexity: O(n * k)—processing n strings of max length k.
• Space Complexity: O(n)—storing all strings in the hash map.

This solution is like a smart librarian sorting books by their secret codes—quick and efficient!

Alternative Solution: Brute Force Comparison

Why an Alternative Approach?

The brute force comparison approach checks every pair of strings to see if they’re shift-equivalent, grouping them manually. It’s slower but shows the concept clearly, making it a great starting point for beginners before tackling the optimized method.

How It Works

• For each string, compare it with all others by shifting one to match the other.
• Group strings that match after shifting.

Step-by-Step Example

Example: strings = ["abc", "bcd", "xyz"]

• Compare "abc":
• To "bcd": Shift "abc" by 1 → "bcd", matches → group.
• To "xyz": Shift "abc" by 23 → "xyz", matches → group.
• Check Others: "bcd" to "xyz" (shift 22) → matches.
• Result: [["abc", "bcd", "xyz"]].

Code for Brute Force Approach

Copy codeclass Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        # Step 1: Helper to check if two strings are shift-equivalent
        def is_shifted(s1, s2):
            if len(s1) != len(s2):
                return False
            if not s1:
                return True
            diff = (ord(s2[0]) - ord(s1[0])) % 26
            for i in range(1, len(s1)):
                if (ord(s2[i]) - ord(s1[i])) % 26 != diff:
                    return False
            return True

        # Step 2: Group strings
        result = []
        used = set()
        for i in range(len(strings)):
            if i in used:
                continue
            group = [strings[i]]
            used.add(i)
            for j in range(i + 1, len(strings)):
                if j not in used and is_shifted(strings[i], strings[j]):
                    group.append(strings[j])
                    used.add(j)
            result.append(group)

        return result

• Time Complexity: O(n² * k)—comparing all pairs.
• Space Complexity: O(n)—storing groups.

It’s intuitive but inefficient.

Comparing the Two Solutions

• Best Solution (Hash Map):
• Pros: O(n * k) time, scalable, elegant.
• Cons: Requires pattern understanding.
• Alternative Solution (Brute Force):
• Pros: Simple logic, visible steps.
• Cons: O(n² * k) time, slow for large lists.

Hash map wins for speed.

Additional Examples and Edge Cases

Single Letters

• ["a", "b"] → [["a"], ["b"]]

Empty Strings

• [""] → [[""]]

Mixed Lengths

• ["ab", "bc", "a"] → [["ab", "bc"], ["a"]]

Both handle these well.

Complexity Breakdown

• Hash Map:
• Time: O(n * k)—linear processing.
• Space: O(n)—group storage.
• Brute Force:
• Time: O(n² * k)—pairwise checks.
• Space: O(n)—results.

Hash map is faster.

Key Takeaways for Beginners

• Normalization: Use differences to identify patterns.
• Hash Map: Group efficiently with keys.
• Brute Force: Compare everything—good for learning.
• Python Tip: ord() unlocks letter math—see [Python Basics](/python/basics).

Final Thoughts: Group Strings Like a Pro

LeetCode 249: Group Shifted Strings in Python is a fun twist on string grouping. The hash map solution offers O(n * k) brilliance, while brute force provides a clear starting point. Want more? Try LeetCode 242: Valid Anagram or LeetCode 438: Find All Anagrams in a String. Ready to shift? Head to Solve LeetCode 249 on LeetCode and group those strings today!