Code Implementation

from collections import defaultdict

class Solution:
    def groupStrings(self, strings):
        groups = defaultdict(list)
        for s in strings:
            # Generate the shift pattern (difference sequence)
            key = []
            for i in range(1, len(s)):
                diff = (ord(s[i]) - ord(s[i-1])) % 26
                key.append(diff)
            groups[tuple(key)].append(s)
        return list(groups.values())
      

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> groups;
        for (const string& s : strings) {
            string key;
            for (int i = 1; i < s.size(); ++i) {
                int diff = (s[i] - s[i-1] + 26) % 26;
                key += to_string(diff) + ",";
            }
            groups[key].push_back(s);
        }
        vector<vector<string>> res;
        for (auto& p : groups) {
            res.push_back(p.second);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strings) {
            StringBuilder key = new StringBuilder();
            for (int i = 1; i < s.length(); i++) {
                int diff = (s.charAt(i) - s.charAt(i-1) + 26) % 26;
                key.append(diff).append(",");
            }
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}
      

/**
 * @param {string[]} strings
 * @return {string[][]}
 */
var groupStrings = function(strings) {
    const groups = {};
    for (let s of strings) {
        let key = [];
        for (let i = 1; i < s.length; i++) {
            let diff = (s.charCodeAt(i) - s.charCodeAt(i-1) + 26) % 26;
            key.push(diff);
        }
        let keyStr = key.join(',');
        if (!groups[keyStr]) groups[keyStr] = [];
        groups[keyStr].push(s);
    }
    return Object.values(groups);
};
      

Problem Description

Given a list of lowercase strings strings, group all strings that belong to the same "shifted sequence." A shifted sequence is defined as a series of strings where each letter in the string can be shifted by the same number of positions (modulo 26, wrapping around from 'z' to 'a') to get another string in the group.

For example, "abc" can be shifted by 1 to become "bcd", or by 2 to become "cde". Strings like "abc", "bcd", and "xyz" all belong to the same shifted group because the difference between consecutive characters is the same for each.

• Each string consists only of lowercase English letters.
• Return a list of groups, where each group contains all strings that belong to the same shifted sequence.
• Each group can be in any order, and the groups themselves can be in any order.

Thought Process

At first glance, we might consider comparing every string with every other string to check if they can be shifted into one another, but this would be inefficient, especially for large inputs.

The key insight is to represent each string by its sequence of differences between adjacent characters. For example, "abc" has differences [1,1] ('b'-'a'=1, 'c'-'b'=1). Any other string with the same difference pattern (modulo 26) belongs to the same group.

By converting each string into its "difference pattern" and grouping strings by this pattern, we can efficiently solve the problem without redundant comparisons.

Solution Approach

• Step 1: For each string, compute its "shift pattern" by calculating the difference between each pair of adjacent characters. Use modulo 26 to handle wrap-around from 'z' to 'a'.
• Step 2: Use a hash map (dictionary) to group strings by their shift pattern. The key is the tuple (or string) of differences, and the value is a list of strings that share this pattern.
• Step 3: After processing all strings, collect the grouped lists from the hash map and return them as the result.

We use a hash map because it allows O(1) insertion and lookup for each pattern, making the grouping process very efficient.

Example Walkthrough

Let's consider strings = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"].

• "abc" → differences: [1,1] → group key: (1,1)
• "bcd" → differences: [1,1] → group key: (1,1)
• "xyz" → differences: [1,1] → group key: (1,1)
• "acef" → differences: [2,2,1] → group key: (2,2,1)
• "az" → differences: [25] → group key: (25)
• "ba" → differences: [25] → group key: (25)
• "a" → differences: [] → group key: ()
• "z" → differences: [] → group key: ()

After grouping by these keys, we get:

• Group (1,1): ["abc", "bcd", "xyz"]
• Group (2,2,1): ["acef"]
• Group (25): ["az", "ba"]
• Group (): ["a", "z"]

Time and Space Complexity

• Brute-force approach: Comparing each pair of strings to check if they are in the same shifted group would take O(N^2 * L), where N is the number of strings and L is the average string length.
• Optimized approach: For each string, we compute its shift pattern in O(L) time, and grouping with a hash map is O(1) per string. So the total time complexity is O(N * L).
• Space complexity: We use O(N * L) space to store the groups in the hash map, as each string and its pattern are stored.

Summary

By representing each string with a difference pattern of its characters, we can efficiently group all shifted strings using a hash map. This approach avoids redundant checks, is easy to implement, and scales well for large inputs. The elegance of the solution comes from reducing the problem to a simple, canonical form for each string, allowing fast grouping and retrieval.