Group Shifted Strings

Group Shifted Strings

What is this problem about?

The Group Shifted Strings interview question asks you to group an array of strings based on their "shifting" property. A string can be shifted by moving every character forward in the alphabet by the same amount (e.g., "abc" shifted by 1 is "bcd", shifted by 25 is "zab"). Strings that can be shifted to match each other belong in the same group.

Why is this asked in interviews?

Companies like Uber and Google ask this Hash Table and String coding problem to test your ability to define a mathematical "signature" for a string. It’s a step up from "Group Anagrams." It evaluates whether you can use modular arithmetic to calculate the relative differences between characters and use that sequence of differences as a dictionary key.

Algorithmic pattern used

This problem relies on a Relative Offset Hashing pattern.

1. For any string, the absolute characters don't matter; only the "distance" between consecutive characters matters.
2. For a string like "acf", the distances are: 'c'-'a' = 2, 'f'-'c' = 3. Signature: 2,3.
3. For "dfi", the distances are: 'f'-'d' = 2, 'i'-'f' = 3. Signature: 2,3.
4. Since they have the same signature, they are in the same shift group.
5. Use a Hash Map where the key is this signature string/tuple, and the value is a list of the original strings.

Example explanation

Strings: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]

1. "abc": diffs are 1, 1. Key: "1,1".
2. "bcd": diffs are 1, 1. Key: "1,1". (Groups with "abc").
3. "az": 'z' - 'a' = 25. Key: "25".
4. "ba": 'a' - 'b' = -1. Because it wraps around the alphabet, we do (-1 + 26) % 26 = 25. Key: "25". (Groups with "az").
5. "a" and "z": Length 1. Key: "". (Group together).

Common mistakes candidates make

• Negative Differences: When calculating char[i] - char[i-1], the result can be negative if the string wraps around 'z' to 'a' (like "ba"). You must handle this using modulo 26: (diff + 26) % 26.
• Comparing to 'a': Shifting every string so its first character becomes 'a' is another valid way to generate a key (e.g., "bcd" shifts back to "abc"), but handling the modulo wrap-around during the shift is where bugs usually occur.

Interview preparation tip

When dealing with circular alphabets or clocks, the formula (value + modulo) % modulo is the safest way to ensure you always get a positive relative distance.