Watch 10 video solutions for Group Shifted Strings, a medium level problem involving Array, Hash Table, String. This walkthrough by Pepcoding has 9,711 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Perform the following shift operations on a string:
"abc" can be right-shifted to "bcd" or "xyz" can be right-shifted to "yza"."bcd" can be left-shifted to "abc" or "yza" can be left-shifted to "xyz".We can keep shifting the string in both directions to form an endless shifting sequence.
"abc" to form the sequence: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...You are given an array of strings strings, group together all strings[i] that belong to the same shifting sequence. You may return the answer in any order.
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"]]
Constraints:
1 <= strings.length <= 2001 <= strings[i].length <= 50strings[i] consists of lowercase English letters.Problem Overview: You receive a list of lowercase strings. Two strings belong in the same group if shifting every character by the same amount (wrapping around from 'z' to 'a') converts one string into the other. The task is to group all strings that share this shifting pattern.
Approach 1: Pairwise Shift Comparison (Brute Force) (Time: O(n^2 * k), Space: O(n))
Compare each string with every other string and check whether they share the same shifting pattern. For two strings, compute the difference between corresponding characters and verify the difference remains consistent modulo 26 across the entire string. If the pattern matches, place them in the same group. This method requires nested iteration over all strings and repeated character comparisons of length k, making it inefficient for larger inputs.
Approach 2: Hash Table with Normalized Shift Pattern (Time: O(n * k), Space: O(n * k))
The key observation: strings in the same shifting sequence have identical relative character differences. Normalize each string by converting it into a pattern representing the difference between consecutive characters modulo 26. For example, "abc" and "bcd" both produce the pattern [1,1]. Use this normalized pattern as the key in a hash table, and append the original string to the corresponding group. Building the key requires iterating over the string once, so the total runtime becomes O(n * k), where n is the number of strings and k is the maximum string length.
The approach relies heavily on fast hash lookups and string iteration, making string processing and array iteration the main operations. The modulo operation ensures circular alphabet behavior when differences cross from 'z' to 'a'.
Recommended for interviews: The hash table approach with normalized shift patterns is the expected solution. It demonstrates recognition of invariant patterns and efficient grouping using hashing. Brute force comparison shows understanding of the shift rule, but the optimized hash-based grouping shows stronger algorithmic thinking and reduces the complexity from quadratic to linear with respect to the number of strings.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pairwise Shift Comparison (Brute Force) | O(n^2 * k) | O(n) | Small input sizes or when first reasoning about the shift property |
| Hash Table with Normalized Shift Pattern | O(n * k) | O(n * k) | General case and optimal interview solution for grouping shifted sequences |