DSA Tracker

Visualize

Isomorphic Strings

One map, and the second rule everybody forgets

time O(n)space O(1)

The obvious half of this problem is easy: walk both strings together and remember what each letter of s turned into, so a letter that shows up again must turn into the same thing. That alone accepts pairs it should reject, because a renaming has to work in BOTH directions — if two different letters of s were allowed to become the same letter of t, you could never rename back, and the strings would not have the same shape. So a second rule is needed: a letter of t may be claimed only once. This trace fails on that second rule, not the first, which is where the usual one-map solution quietly gives the wrong answer.

Details

Animated on: s = "buttoning", t = "different" — can every letter of s be renamed to a letter of t consistently? Each cell shows the pairing one index demands.

Problem:Isomorphic StringsEasy

One map, and the second rule everybody forgets

step 1 / 8

b→d
[0]
u→i
[1]
t→f
[2]
t→f
[3]
o→e
[4]
n→r
[5]
i→e
[6]
n→n
[7]
g→t
[8]

Each cell is the demand one index makes: "b→d" means index 0 needs 'b' to become 'd'. A pairing works only if it is a ONE-TO-ONE renaming, so two rules have to hold at every index: a letter of s must always become the SAME letter of t, and no two different letters of s may claim the same letter of t.

Pseudocode
1FUNCTION isIsomorphic(s, t)
2  map <- EMPTY MAP
3  FOR i <- 0 TO LENGTH(s) - 1
4    IF s[i] IN map
5      IF map[s[i]] != t[i]
6        RETURN false
7    ELSE
8      IF t[i] IN VALUES(map)
9        RETURN false
10      map[s[i]] <- t[i]
11  RETURN true

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Each cell is the demand one index makes: "b→d" means index 0 needs 'b' to become 'd'. A pairing works only if it is a ONE-TO-ONE renaming, so two rules have to hold at every index: a letter of s must always become the SAME letter of t, and no two different letters of s may claim the same letter of t.
  2. 'b' has no mapping yet and 'd' is still unclaimed, so both rules are satisfied — lock 'b'→'d'. Map now {b→d}, claiming 1 of t's letters.
  3. 'u' has no mapping yet and 'i' is still unclaimed, so both rules are satisfied — lock 'u'→'i'. Map now {b→d, u→i}, claiming 2 of t's letters.
  4. 't' has no mapping yet and 'f' is still unclaimed, so both rules are satisfied — lock 't'→'f'. Map now {b→d, u→i, t→f}, claiming 3 of t's letters.
  5. 't' is already locked to 'f' and index 3 demands 'f' — they agree, so this index costs nothing and teaches nothing new. Map unchanged: {b→d, u→i, t→f}.
  6. 'o' has no mapping yet and 'e' is still unclaimed, so both rules are satisfied — lock 'o'→'e'. Map now {b→d, u→i, t→f, o→e}, claiming 4 of t's letters.
  7. 'n' has no mapping yet and 'r' is still unclaimed, so both rules are satisfied — lock 'n'→'r'. Map now {b→d, u→i, t→f, o→e, n→r}, claiming 5 of t's letters.
  8. 'i' is new, so rule one is silent here — and this is exactly the trap. 'e' was already claimed by 'o' back at index 4, so letting 'i' take it too would merge two distinct letters into one. A renaming has to be reversible, so this fails: {b→d, u→i, t→f, o→e, n→r} has no room for 'i'→'e'.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Isomorphic Strings in the editorAll Strings problemsBack to roadmap