Free Hashing lessonsHashing · Stage 1 · Grouping by key · Step 2

A consistent code

Check whether one string can be turned into another by renaming letters. About 9 minutes.

A renaming is a map

"paper" and "title" have the same shape: rename p to t, a to i, e to l and r to e, and one becomes the other. Like a code where each letter always stands for one other letter.

Walk both strings side by side and write down each pairing in a map. If a letter ever needs a different partner than it had before, it isn't a consistent renaming.

Each letter: always gets the same partner.

s = "paper", t = "title"

s→t: {p: t}
t→s: {t: p}

p pairs with t. Write it in both maps: p → t and t → p.

Move 1 of 5

Two letters can't share a partner

There's a second trap. "ab" to "aa": a pairs with a, b pairs with a. Each letter kept one partner, yet two different letters became the same one. That's not a renaming.

So keep a second map going the other way, from the second string back to the first. Both maps must stay consistent.

Check both directions: one map each way.

In code

forward, back = {}, {}
for a, b in zip(s, t):
    if forward.get(a, b) != b:
        return False
    if back.get(b, a) != a:
        return False
    forward[a], back[b] = b, a
return True

Quick check

Is "badc" to "baba" a valid renaming?

ANo
BYes
CNo, the lengths differ

Show the answer

No. b becomes b and d becomes b: two letters would share the partner b.

Your problem

Same shape?

Two strings of the same length have the same shape if you can rename the characters of s (each character to exactly one character, no two to the same one) to get t. Return true if they do.

Example

s = "paper", t = "title" → true

0 ≤ length ≤ 100,000 · same length · printable ASCII

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.