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.
We use a hash table g to store each string after shifting and with the first character as 'a'. That is, g[t] represents the set of all strings that become t after shifting.
We iterate through each string. For each string, we calculate its shifted string t, and then add it to g[t].
Finally, we take out all the values in g, which is the answer.
The time complexity is O(L) and the space complexity is O(L), where L is the sum of the lengths of all 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 |
Group Shifted Strings | Hashmap Interview Questions Playlist • Pepcoding • 9,711 views views
Watch 9 more video solutions →Practice Group Shifted Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor