Skip to main content
Talentd

Group Shifted Strings - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableString6 min readAsked at: Meta, Uber, Google +1
Practice this problem

Problem Statement

Perform the following shift operations on a string:

  • Right shift: Replace every letter with the successive letter of the English alphabet, where 'z' is replaced by 'a'. For example, "abc" can be right-shifted to "bcd" or "xyz" can be right-shifted to "yza".
  • Left shift: Replace every letter with the preceding letter of the English alphabet, where 'a' is replaced by 'z'. For example, "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.

  • For example, shift "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 <= 200
  • 1 <= strings[i].length <= 50
  • strings[i] consists of lowercase English letters.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 PatternO(n * k)O(n * k)General case and optimal interview solution for grouping shifted sequences

Video Solution

Group Shifted Strings | Hashmap Interview Questions Playlist • Pepcoding • 9,817 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Group Shifted Strings easy or hard?
Group Shifted Strings is considered a Medium difficulty problem. The main challenge is recognizing that strings can be grouped by their relative character differences rather than their absolute characters.
Group Shifted Strings Python/Java solution
The typical Python or Java solution builds a hash map where the key is a tuple or string representing character differences modulo 26. Each input string is converted to this pattern and appended to the corresponding group. The algorithm runs in O(n * k) time.
How to solve Group Shifted Strings in O(n)?
Strict O(n) isn't possible because each string must be read character by character. The closest optimal solution is O(n * k), achieved by computing a normalized shift pattern for each string and grouping them using a hash table.
What is the best approach for Group Shifted Strings?
The best approach uses a hash table with a normalized shift pattern as the key. For each string, compute the differences between adjacent characters modulo 26 and store the string in a map under that pattern. Strings with identical patterns belong to the same shifting sequence. This reduces the runtime to O(n * k).
Is Group Shifted Strings asked at Google/Amazon/Meta?
Group Shifted Strings is a common medium-level string and hashing problem frequently discussed in interviews and coding platforms. Variations of pattern normalization and grouping using hash maps appear in interviews at companies like Google, Amazon, and Meta.
What data structure is used in Group Shifted Strings?
A hash table (hash map) is the primary data structure. The key represents the normalized shift pattern of a string, and the value stores a list of strings that share that pattern.
What is the time complexity of Group Shifted Strings?
The optimal solution runs in O(n * k) time, where n is the number of strings and k is the maximum length of a string. Each string is scanned once to compute its shift pattern, and inserting into the hash table is O(1) on average.

Ready to solve this problem?

Practice Group Shifted Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Maximum Number of String Pairs

Next

Group Anagrams