0594MediumArrayHash TableString

Dial Lock Families

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

An old cabinet is opened by a dial whose setting is written as a word of lowercase letters. Clicking the dial forward one notch advances every letter of the setting one step along the alphabet, and a letter sitting on z comes back round to a. One notch therefore takes the setting az to ba, and two notches take it to cb.

You are given strings, a list of settings found written on scraps of paper. Two settings belong to the same family when some number of notches, possibly zero, carries one of them to the other. A setting always shares a family with itself, and settings of different lengths can never share one.

Return the families as a list of lists. Every entry of strings must appear once in the answer, so a setting written on two scraps appears twice inside its family. The families may come back in any order, and so may the settings inside each family.

Examples

Example 1

Input: strings = ["az", "ba", "by", "cz"]
Output: [["az", "ba"], ["by", "cz"]]

One notch takes `az` to `ba`, so those two share a family. Turning `by` forward reaches `cz` only after 27 notches worth of movement on the first letter but 28 on the second, so no single number of notches links them and each stands alone.

Example 2

Input: strings = ["mno", "nop", "ab", "bc", "cd"]
Output: [["mno", "nop"], ["ab", "bc", "cd"]]

`mno` reaches `nop` in one notch. Among the two-letter settings, one notch takes `ab` to `bc` and another takes `bc` to `cd`, so all three sit in one family, which cannot include the three-letter settings.

Example 3

Input: strings = ["ab", "ac", "bc"]
Output: [["ab", "bc"], ["ac"]]

One notch carries `ab` to `bc`. No number of notches carries `ab` to `ac`, because the first letter would need one notch while the second would need two.

Constraints

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

The groups you return, and the values inside each group, may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def group_strings(strings: list[str]) -> list[list[str]]:

Java

public List<List<String>> groupStrings(String[] strings)

The intended approach

Time O(L) where L is the total number of letters across all settings.Space O(L) for the keys and the grouped settings that are returned.

Clicking the dial moves every letter of a setting by the same amount, so the distance from each letter to the setting's own first letter, counted forward around the ring of 26 letters, is untouched. Build that list of distances for each setting and use it as a dictionary key: two settings land on the same key exactly when they share a family, since equal length is already implied by equal key length. Collecting the values of the dictionary gives the families.

Pythonentry point: group_strings

def group_strings(strings):
    # O(total number of letters) time and space. Turning the dial changes every
    # letter by the same amount, so the gap between each letter and the first
    # letter of the same setting, measured around the 26-letter ring, never
    # changes. That list of gaps is therefore a fingerprint of the family.
    families = {}
    for setting in strings:
        base = ord(setting[0])
        gaps = []
        for ch in setting:
            gaps.append((ord(ch) - base) % 26)
        key = tuple(gaps)
        if key in families:
            families[key].append(setting)
        else:
            families[key] = [setting]
    return list(families.values())

The obvious version

Compare every pair of settings directly: they are related when they have the same length and every letter of one is the same number of notches ahead of the matching letter of the other, counted around the ring. Merge related pairs with a disjoint-set structure, then read off the members of each set.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_group_strings(strings):
    n = len(strings)
    parent_of = list(range(n))

    def root(x):
        while parent_of[x] != x:
            parent_of[x] = parent_of[parent_of[x]]
            x = parent_of[x]
        return x

    def related(a, b):
        if len(a) != len(b):
            return False
        notches = (ord(b[0]) - ord(a[0])) % 26
        for i in range(len(a)):
            if (ord(b[i]) - ord(a[i])) % 26 != notches:
                return False
        return True

    for i in range(n):
        for j in range(i + 1, n):
            if related(strings[i], strings[j]):
                ri, rj = root(i), root(j)
                if ri != rj:
                    parent_of[ri] = rj
    buckets = {}
    for i in range(n):
        r = root(i)
        if r not in buckets:
            buckets[r] = []
        buckets[r].append(strings[i])
    return list(buckets.values())

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in