Group Shifted Strings

Medium Arrays & Hashing Hashing Original on LeetCode

Reported atGoogle

Group Shifted Strings is a medium arrays & hashing problem solved with the hashing pattern. The best approach, optimal (normalise to start with 'a'), runs in O(n · k) time and O(n · k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (compare every pair) up.

Problem

Shifting a lowercase string means moving every letter one step forward in the alphabet, with z wrapping around to a. For example, shifting "azy" once gives "baz". Repeating the shift produces a whole sequence of strings, such as "abc" -> "bcd" -> ... -> "zab" -> "abc".

You are given an array strings. Group together all strings that belong to the same shifting sequence, that is, strings where one can be turned into the other by shifting it some number of times.

Return the list of groups. The groups, and the strings inside each group, can be in any order.

Examples

Example 1

Input
strings = ["bcd", "xyz", "ace", "mno", "bdf", "q", "k"]
Output
[["bcd", "xyz", "mno"], ["ace", "bdf"], ["q", "k"]]
Why
bcd, xyz and mno are three consecutive letters; ace and bdf step by 2; every single letter can be shifted into any other single letter.

Example 2

Input
strings = ["za", "ab", "ba"]
Output
[["za", "ab"], ["ba"]]
Why
Shifting za by one wraps z to a and a to b, giving ab. ba steps backwards, so it is alone.

Example 3

Input
strings = ["hello"]
Output
[["hello"]]
Why
One string forms one group.

Constraints

  • 1 <= strings.length <= 200
  • 1 <= strings[i].length <= 50
  • strings[i] consists of lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (compare every pair)O(n² · k)O(n · k)
Optimal (normalise to start with 'a')O(n · k)O(n · k)

1Brute force (compare every pair)

TimeO(n² · k)Up to n² / 2 pairs, each checked in O(k) for strings of length k.
SpaceO(n · k)The answer holds every string; the flags take O(n).

Take the first string without a group, open a new group with it, and test every later ungrouped string against it. Two strings match when they have the same length and every letter differs by the same shift (modulo 26).

  1. Keep a used[] flag per string.
  2. For each unused i: start a group with strings[i] and mark it used.
  3. For each unused j > i: if sameShift(strings[i], strings[j]), add strings[j] to the group and mark it used.
  4. sameShift: lengths equal and (b[k] - a[k] + 26) % 26 is the same for every position k.
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        int n = strings.length;
        boolean[] used = new boolean[n];
        List<List<String>> groups = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            List<String> group = new ArrayList<>();
            group.add(strings[i]);
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && sameShift(strings[i], strings[j])) {
                    used[j] = true;
                    group.add(strings[j]);
                }
            }
            groups.add(group);
        }
        return groups;
    }

    private boolean sameShift(String a, String b) {
        if (a.length() != b.length()) return false;
        int shift = (b.charAt(0) - a.charAt(0) + 26) % 26;
        for (int k = 1; k < a.length(); k++) {
            if ((b.charAt(k) - a.charAt(k) + 26) % 26 != shift) return false;
        }
        return true;
    }
}

2Optimal (normalise to start with 'a')

TimeO(n · k)Each string is scanned once to build its key.
SpaceO(n · k)The map stores every string and one key per group.

Shift every string backwards until its first letter is a. Strings from the same group all collapse to the same normalised string, so it works as a hash map key. One pass over the input fills the buckets.

  1. Create a map from key to list of strings.
  2. For each string s: offset = s[0] - 'a'; build key by replacing each letter c with (c - 'a' - offset + 26) % 26 + 'a'.
  3. Append s to map[key].
  4. Return all lists in the map.
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strings) {
            int offset = s.charAt(0) - 'a';
            char[] key = new char[s.length()];
            for (int k = 0; k < s.length(); k++) {
                key[k] = (char) ('a' + (s.charAt(k) - 'a' - offset + 26) % 26);
            }
            groups.computeIfAbsent(new String(key), x -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

Edge cases to test

  • Wrap-around from z to a (for example az and ba belong together)
  • Strings of different lengths can never be in the same group
  • All single-letter strings form one group
  • Duplicate strings stay together in one group

Hints

Hint 1

Two strings of the same length are in one group exactly when the gap between each pair of neighbouring letters is the same in both.

Hint 2

Shift every string so that it starts with a. All members of a group turn into the same normalised string.

Hint 3

Use that normalised string (or the list of gaps taken modulo 26) as a hash map key.

FAQ

What is the best time complexity for Group Shifted Strings?

Optimal (normalise to start with 'a') runs in O(n · k) time and O(n · k) extra space. Each string is scanned once to build its key.

Which pattern does Group Shifted Strings use?

It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.

Is there a brute force solution for Group Shifted Strings?

Yes. Brute force (compare every pair) takes O(n² · k) time and O(n · k) space. Take the first string without a group, open a new group with it, and test every later ungrouped string against it.

Which edge cases should I test for Group Shifted Strings?

Wrap-around from z to a (for example az and ba belong together); Strings of different lengths can never be in the same group; All single-letter strings form one group; Duplicate strings stay together in one group.