Problem

We can shift a string by shifting each of its letters to its successive letter.

  • For example, "abc" can be shifted to be "bcd".

We can keep shifting the string to form a sequence.

  • For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.

Examples

Example 1:

Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

Example 2:

Input: strings = ["a"]
Output: [["a"]]

Solution

Method 1 - Using the Map

To solve the problem of grouping strings that belong to the same shifting sequence, we need to identify what makes two strings belong to the same group.

Key Insight:

  • Two strings belong to the same shifting sequence if the difference between consecutive letters is the same modulo 26. This difference can serve as a unique key for each shifting sequence.

Here are the steps:

  1. Calculate Key:
    • Convert each string into a key representing its shifting pattern. This key will be a tuple of differences between each consecutive character modulo 26.
  2. Group Strings:
    • Use a dictionary to map the key to all strings that have the same shifting pattern.

Code

Java
public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strings) {
            String key = getKey(str);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        
        List<List<String>> ans = new ArrayList<>();
        for (List<String> group : map.values()) {
            ans.add(group);
        }
        
        return ans;
    }
    
    private String getKey(String str) {
        StringBuilder key = new StringBuilder();
        for (int i = 1; i < str.length(); i++) {
            int diff = str.charAt(i) - str.charAt(i - 1);
            if (diff < 0) {
                diff += 26;
            }
            key.append(diff).append(",");
        }
        return key.toString();
    }
}
Python
 class Solution:
     def groupStrings(self, strings: List[str]) -> List[List[str]]:
         def get_key(s: str) -> str:
             key = []
             for i in range(1, len(s)):
                 diff = (ord(s[i]) - ord(s[i - 1])) % 26
                 key.append(diff)
             return tuple(key)
         
         map: Dict[tuple, List[str]] = defaultdict(list)
         for s in strings:
             key = get_key(s)
             map[key].append(s)
         
         return list(map.values())

Complexity

  • ⏰ Time complexity: O(n * m), where n is the number of strings and m is the average length of each string. This accounts for converting strings to their keys and grouping them.
  • 🧺 Space complexity: O(n * m), to store the strings in the dictionary.