Group Shifted Strings
Problem
Two strings are in the same shift sequence if one can be obtained from the other by shifting each character. Group strings that belong to the same shift sequence.
["abc","bcd","acef","xyz","az","ba","a","z"][["a","z"],["abc","bcd","xyz"],["acef"],["az","ba"]]def group_strings(strs):
groups = {}
for s in strs:
key = tuple((ord(s[i+1]) - ord(s[i])) % 26 for i in range(len(s) - 1))
groups.setdefault(key, []).append(s)
return list(groups.values())function groupStrings(strs) {
const m = new Map();
for (const s of strs) {
const key = [];
for (let i = 0; i + 1 < s.length; i++) {
key.push(((s.charCodeAt(i+1) - s.charCodeAt(i)) % 26 + 26) % 26);
}
const k = key.join(",");
if (!m.has(k)) m.set(k, []);
m.get(k).push(s);
}
return [...m.values()];
}class Solution {
public List> groupStrings(String[] strs) {
Map> m = new HashMap<>();
for (String s : strs) {
StringBuilder key = new StringBuilder();
for (int i = 0; i + 1 < s.length(); i++) {
key.append((s.charAt(i+1) - s.charAt(i) + 26) % 26).append(',');
}
m.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(m.values());
}
} vector> groupStrings(vector& strs) {
unordered_map> m;
for (auto& s : strs) {
string key;
for (int i = 0; i + 1 < (int)s.size(); i++) {
int d = ((s[i+1] - s[i]) % 26 + 26) % 26;
key += to_string(d) + ",";
}
m[key].push_back(s);
}
vector> out;
for (auto& [_, v] : m) out.push_back(v);
return out;
} Explanation
Shifting a string moves every letter forward by the same amount, wrapping z back to a. So what truly identifies a shift family is not the letters themselves but the gaps between consecutive letters, which never change when you shift.
For each string we compute the gap sequence (ord(s[i+1]) - ord(s[i])) % 26 for every adjacent pair and use that tuple as a hash map key. Strings with the same gaps drop into the same bucket.
The mod 26 is what handles wrap-around: from a to z the raw gap is 25, and from z to a it is -25, but -25 % 26 is also 1... the point is mod keeps every gap in 0..25 so equivalent shifts match.
Example: "abc" has gaps [1,1] and "bcd" also has gaps [1,1], so they group together. "az" and "ba" both have a single gap of 1 (z→a wraps), so they pair up too.
Single characters have no gaps, giving an empty key, so all length-one strings land in one group. We return the list of all buckets.