⚡Flashcard Drill➔
NeetCode #20LC-249MediumArrays & HashingNC Algo100
← Back to All Problems

#20 · #249 · Group Shifted Strings(移位字符串分组)

📌 Problem Statement & Constraints

Given a list of strings where all strings are of the same length, group all strings that belong to the same shifting sequence. A shifting sequence is formed by rotating every character of a string by the same amount. Return the groups in any order. Constraints: 1 <= strings.length <= 200, 1 <= strings[i].length <= 50.

💡 Core Algorithmic Approaches

  1. A shift changes every character by the same amount, so the differences between consecutive characters are shift-invariant.
  2. For a string s, build the key tuple((ord(s[i]) - ord(s[i-1])) % 26 for i in 1..len-1).
  3. The modulo is essential: a -> z wraps around, so a raw difference would be -25 instead of 1.
  4. Single-character strings all produce the empty tuple and therefore group together -- which is correct, since any single character can be shifted into any other.

💻 Benchmark Python3 Implementation

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        from collections import defaultdict
        groups = defaultdict(list)
        for s in strings:
            # shift-invariant key: consecutive character deltas, wrapped mod 26
            key = tuple((ord(s[i]) - ord(s[i - 1])) % 26 for i in range(1, len(s)))
            groups[key].append(s)
        return list(groups.values())

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * k) where n is the number of strings and k the string length: each string is hashed in one pass.
💾 Space Complexity
O(n * k) for the groups and the keys.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the % 26: the difference ord('a') - ord('z') is -25, which is the same shift as +1, so the keys would fail to match.
  • Using the first character as part of the key: that is exactly what a shift changes, so it must be excluded.
  • Using a list as the dict key: unhashable; wrap it in tuple.
  • Special-casing single-character strings: the empty tuple already groups them correctly, so no branch is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems