DSA problem
Group Shifted Strings
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: "abc" -> "bcd" -> ... -> "xyz". Note that shifting wraps around, so "z" shifts to "a".
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.
Two strings belong to the same group if one can be obtained from the other by repeatedly applying the shift operation. Strings of the same length whose consecutive character gaps match (modulo 26) are in the same group.
Examples
Example 1
Input:
strings = ["abc","bcd","acef","xyz","az","ba","a","z"]Output:
[["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]Explanation: "abc", "bcd", and "xyz" all have consecutive gaps of (+1, +1) so they shift into each other. "az" and "ba" both have a gap of (+1) modulo 26. "a" and "z" are single characters with no gaps. "acef" has unique gaps and is alone.
Example 2
Input:
strings = ["a"]Output:
[["a"]]Explanation: A single string forms a group by itself.
Example 3
Input:
strings = ["abc","abd"]Output:
[["abc"],["abd"]]Explanation: "abc" has gaps (+1,+1) while "abd" has gaps (+1,+2), so they belong to different shifting sequences.
Constraints
- 1 <= strings.length <= 200
- 1 <= strings[i].length <= 50
- strings[i] consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.