0133EasyHash TableString

Interchangeable Route Codes

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.

Two depots label the same delivery run with their own character codes, first and second, of equal length. Dispatch wants to know whether the two labels describe the same run under a consistent relabelling of characters.

Call the codes interchangeable when there is a substitution table that turns first into second position by position, subject to two rules:

every occurrence of a given character in first must be substituted by the same character in second
no two different characters of first may be substituted by the same character of second

A character is allowed to substitute to itself. Codes may contain any ASCII characters, including digits, spaces and punctuation, and uppercase is a different character from lowercase. Return true when the codes are interchangeable and false otherwise.

Examples

Example 1

Input: first = "mim", second = "tot"
Output: true

Substituting m for t and i for o rewrites the first label as the second, and the repeated character stays consistent at both ends.

Example 2

Input: first = "kk", second = "qr"
Output: false

The single character of the first label would have to become two different characters, which no substitution table allows.

Example 3

Input: first = "dip dip", second = "kop kop"
Output: true

The blank counts as an ordinary character and maps to itself, while d, i and p take three distinct partners.

Constraints

1 <= first.length <= 5 * 10^4
second.length == first.length
first and second consist of any valid ascii characters

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 codes_interchangeable(first: str, second: str) -> bool:

Java

public boolean codesInterchangeable(String first, String second)

The intended approach

Time O(n)Space O(1), bounded by the size of the ASCII alphabet

Scan the two codes together and grow the substitution table on the fly. One dictionary records what each character of `first` was committed to; a second dictionary records which character of `first` already claimed a given character of `second`. A clash in either dictionary breaks one of the two rules, so the answer is false. Both tables are needed: a single table only enforces consistency in one direction.

Pythonentry point: codes_interchangeable

def codes_interchangeable(first, second):
    if len(first) != len(second):
        return False
    forward = {}
    backward = {}
    for a, b in zip(first, second):
        if a in forward:
            if forward[a] != b:
                return False
        elif b in backward:
            return False
        else:
            forward[a] = b
            backward[b] = a
    return True

The obvious version

Rewrite each code independently into a canonical shape: replace every character by the order in which it first appeared. Two codes are interchangeable exactly when their shapes match. No substitution table is ever built.

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_codes_interchangeable(first, second):
    def fingerprint(code):
        rank = {}
        shape = []
        for ch in code:
            if ch not in rank:
                rank[ch] = len(rank)
            shape.append(rank[ch])
        return shape
    return fingerprint(first) == fingerprint(second)

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