Group Shifted Strings - Solution & Explanation

Problem Overview: You are given a list of lowercase strings. Two strings belong in the same group if shifting every character in one string by the same number of positions in the alphabet transforms it into the other (wrapping around from 'z' to 'a'). The task is to group all strings that share this shifting pattern.

Approach 1: Pairwise Comparison (Brute Force) (Time: O(n^2 * k), Space: O(n))

Compare every pair of strings and check if they belong to the same shifting sequence. Two strings match if the difference between consecutive characters is identical modulo 26. For each unvisited string, iterate through the remaining strings and verify the shift pattern character by character. Valid matches get grouped together. This approach is straightforward but inefficient because each comparison scans up to k characters and happens for many pairs.

Approach 2: Normalize by Shift Pattern with Hash Map (Time: O(n * k), Space: O(n * k))

The key observation: all strings in the same group share the same relative character differences. Normalize each string by converting it into a canonical pattern. For example, shift every character so the first character becomes 'a'. The string "bcd" becomes "abc", and "xyz" also becomes "abc". Use this normalized representation as a key in a hash map. Iterate through each string, compute its normalized pattern using modulo arithmetic, and append the original string to the corresponding list. This relies heavily on fast lookups using a hash table while processing characters from the string. The input list itself is an array of strings.

Approach 3: Difference Signature Key (Time: O(n * k), Space: O(n * k))

Instead of shifting characters to start at 'a', compute a signature representing the difference between adjacent characters. For example, "acd" produces the signature [2,1] because c-a=2 and d-c=1. Strings like "dfg" generate the same signature. Store these difference arrays (or encoded strings) as hash map keys and group the original strings accordingly. This method avoids modifying characters and focuses purely on relative spacing in the alphabet.

Recommended for interviews: The hash map normalization approach is the expected solution. It runs in O(n * k) time and cleanly captures the invariant property of shifted sequences. Mentioning the brute force comparison shows you understand the problem definition, but implementing the normalized pattern or difference signature demonstrates stronger algorithmic thinking.