249. Group Shifted Strings
Model: qwen3.5:9b
Topics: Hash Table,String
FAANG asked: 1
Acceptance rate: 58.5%
Problem Breakdown
We are given an array of lowercase English strings. Two strings belong in the same group if one can be transformed into another by cyclically shifting every character to its successor letter repeatedly (e.g., ‘a’ -> ‘b’, …, ‘z’ -> ‘a’). We need to partition all input strings into these equivalence groups and return them as a list of lists.
Inputs: A list strings containing non-empty lowercase English letters.
Outputs: A 2D list where each inner list contains the original strings belonging to one shifting sequence. The order of groups does not matter, nor does the order within groups (though usually preserving input relative order is cleaner).
Constraints & Edge Cases:
- Strings can be length 1 up to 50.
- Input array size up to 200.
- Implicitly, ‘z’ shifts back to ‘a’. This cyclic nature means we must use modulo arithmetic (mod 26) for character differences.
Intuition
A brute-force solution would compare every pair of strings in the input list using a helper function that checks if string1 can be shifted into string2. If they match, add to same group; otherwise create new groups. This is O(N^3 * L) or worse because we’d need nested loops for grouping and string comparisons.
The key insight lies in what property remains invariant under shifting?
If I shift “abc” by +1 to get “bcd”, the relative distance between adjacent characters stays constant modulo 26.
However, an even simpler canonical form exists: For any string s, if we subtract the ASCII value of its first character from every other character in that same string (modulo 26), all strings belonging to the same shifting sequence will produce identical tuples.
Why? Because a global shift adds a constant offset to every character index. When calculating (char[i] - char[0]), the added offsets cancel out: . Thus, this relative difference signature is unique for each shifting sequence and invariant under global shifts.
Approach
- Initialize a hash map (
defaultdict(list)). The key will be the canonical tuple representing the string’s shift pattern; the value will be a list of strings matching that pattern. - Iterate through every string in
strings. - For each string, compute its signature:
- Create an empty tuple for the signature.
- Loop over characters at index . Calculate
(ord(char[i]) - ord(string[0])) % 26and append to a list (or directly build tuple). Note thatstring[0]itself yields difference 0, which is consistent across all shifts of the same sequence.
- Convert this signature list into an immutable key (tuple) for dictionary storage.
- Append the original string to the corresponding group in the hash map.
- Return the values of the hash map as a list of lists.
Complexity Analysis
- Time: , where is the number of strings and is the maximum length of a string. We iterate through each character exactly once to compute signatures. Dictionary operations are O(1) on average (assuming hash collisions don’t degrade significantly).
- Space: , where is the number of unique groups found and accounts for storing all input strings in the output structure. In worst case (all distinct), space approaches O(N * L) to store keys and values.
Solution
from collections import defaultdict
def groupShiftedStrings(strings):
# Map from canonical signature tuple -> list of original strings
groups = defaultdict(list)
for s in strings:
if not s:
continue
# Compute relative differences modulo 26 starting from the first character.
# (ord(c) - ord(s[0])) % 26 ensures cyclic shift invariance.
signature = tuple((ord(char) - ord(s[0])) % 26 for char in s)
groups[signature].append(s)
return list(groups.values())
# Example usage:
# print(groupShiftedStrings(["abc","bcd","acef","xyz","az","ba","a","z"]))
Edge Cases Handled
- Single character strings: The signature calculation results in a tuple
(0,). All single-character strings map to this key, correctly grouping them together (e.g., “a” and “b” are considered part of the same cyclic sequence). - Empty input list: Returns an empty list
[]naturally. - Strings with identical characters (e.g., “aaa”): Signature becomes
(0, 0, ...). Correctly grouped only with other strings that have zero relative shift between all adjacent chars modulo 26. - Cyclic wrapping (‘z’ -> ‘a’): Handled by the
% 26operator in signature calculation (e.g.,ord('a') - ord('z') = -25, which becomes1mod 26).