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
- A shift changes every character by the same amount, so the differences between consecutive characters are shift-invariant.
- For a string
s, build the keytuple((ord(s[i]) - ord(s[i-1])) % 26 for i in 1..len-1). - The modulo is essential:
a -> zwraps around, so a raw difference would be-25instead of1. - 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 differenceord('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.