Isomorphic Strings: Why You Need a Map in Each Direction

You're given two strings s and t of the same length. I'd like you to say whether t can be made from s by renaming letters, where every copy of a letter is renamed to the same new letter and no two different letters are allowed to end up with the same name. A letter may also keep its own name.

Examples

Input	Output	Why
`s = "egg", t = "add"`	`true`	If you rename e to a and g to d you get add, and nothing gets renamed twice.
`s = "foo", t = "bar"`	`false`	The two copies of o would have to turn into a and into r at the same time.
`s = "badc", t = "baba"`	`false`	Going from s to t looks fine, but b and d would both have to be renamed to b and that isn't allowed.

Constraints

1 ≤ n ≤ 5 × 10⁴
s.length = t.length
s and t hold printable ASCII characters

Hints

Hint 1

I'd walk along both strings together and write down what each letter of s has been renamed to so far, because the first time you see a letter you're free to choose and every time after that you aren't.

Hint 2

That one map catches foo and bar, but try it on badc and baba and you'll see it says yes when the answer is no, so ask yourself what it isn't checking.

Hint 3

Keep a second map from the letters of t back to the letters of s, and only say yes if both of them stay consistent all the way along the strings.

Where people lose marks

Keeping only the map from s to t. It passes the examples that people usually try first and then says yes on badc and baba, so I'd always test a case where two letters of s collide on one letter of t.
Checking whether t[i] already appears somewhere among the values of the first map. That gets the right answer but it's a scan over the map at every step, and the second map does the same job with one lookup.
Forgetting that the strings can hold any printable character at all, spaces and digits included, so a fixed array of 26 slots will break on a space or a digit and you'd want 128 slots or a hash map.

Dry run on `"badc","baba"`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 4

Step 1 / 4

s
b0a1d2c3
t
b0a1b2a3
s→t{}t→s{}
We walk along "badc" and "baba" together, keeping one map from the letters of s to the letters of t and another one going back the other way.
Step 2 / 4

s
b0ia1d2c3
t
b0ia1b2a3
s→t{b→b}t→s{b→b}
At position 0 neither b nor b has a partner yet, so we pair them up in both maps.
Step 3 / 4

s
b0a1id2c3
t
b0a1ib2a3
s→t{b→b, a→a}t→s{b→b, a→a}
At position 1 neither a nor a has a partner yet, so we pair them up in both maps.
Step 4 / 4

s
b0a1d2ic3
t
b0a1b2ia3
s→t{b→b, a→a}t→s{b→b, a→a}answerfalse
At position 2 we'd pair d with b, but b already came from b and here it would have to come from d, which is the clash that only the second map can see, so the answer is false.

How to think about it

You'll find this one under the name Isomorphic Strings, and I like it because the obvious solution is nearly right and the bit that's missing teaches you something. What you're really checking is that the renaming is a one-to-one match between the letters of s and the letters of t, which means it has to work in both directions at once.

So you walk along the two strings side by side and keep two hash maps. One remembers what each letter of s was sent to and the other remembers which letter of s each letter of t came from. At every position you look both letters up, and if either map already holds a different partner you can stop and say no. If neither does you record the pair in both maps and carry on, and if you reach the end then the renaming exists and you've built it as you went.

The map from s to t on its own only stops one letter of s going to two places, and the map back is what stops two letters of s landing on the same letter of t. That's exactly the difference between badc against baba, where the first map is perfectly happy, and the right answer of no.

Complexity. Time O(n) · Space O(σ) for an alphabet of σ characters

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    fwd, back = {}, {}              # s -> t and t -> s
    for a, b in zip(s, t):
        if fwd.get(a, b) != b or back.get(b, a) != a:
            return False            # one side already has a different partner
        fwd[a] = b
        back[b] = a
    return True

#include <string>
using namespace std;

bool solve(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int fwd[256], back[256];                 // s -> t and t -> s, -1 for no partner yet
    for (int c = 0; c < 256; c++) fwd[c] = back[c] = -1;
    for (size_t i = 0; i < s.size(); i++) {
        unsigned char a = s[i], b = t[i];
        if ((fwd[a] != -1 && fwd[a] != b) || (back[b] != -1 && back[b] != a)) return false;
        fwd[a] = b;
        back[b] = a;
    }
    return true;
}

import java.util.*;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Character> fwd = new HashMap<>(), back = new HashMap<>(); // s -> t and t -> s
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);
            Character fa = fwd.get(a), bb = back.get(b);
            if ((fa != null && fa != b) || (bb != null && bb != a)) return false;
            fwd.put(a, b);
            back.put(b, a);
        }
        return true;
    }
}

function isIsomorphic(s, t) {
  if (s.length !== t.length) return false;
  const fwd = new Map(), back = new Map(); // s -> t and t -> s
  for (let i = 0; i < s.length; i++) {
    const a = s[i], b = t[i];
    if ((fwd.has(a) && fwd.get(a) !== b) || (back.has(b) && back.get(b) !== a)) return false;
    fwd.set(a, b);
    back.set(b, a);
  }
  return true;
}

use std::collections::HashMap;

fn solve(s: &str, t: &str) -> bool {
    if s.len() != t.len() {
        return false;
    }
    let mut fwd: HashMap<char, char> = HashMap::new(); // s -> t
    let mut back: HashMap<char, char> = HashMap::new(); // t -> s
    for (a, b) in s.chars().zip(t.chars()) {
        if *fwd.entry(a).or_insert(b) != b || *back.entry(b).or_insert(a) != a {
            return false;
        }
    }
    true
}

import qualified Data.Map.Strict as M

-- Walk both strings with a map each way; stop at the first pair that clashes with either map.
solve :: String -> String -> Bool
solve s t = length s == length t && go M.empty M.empty (zip s t)
  where
    go _ _ [] = True
    go f b ((x, y) : rest) =
      M.findWithDefault y x f == y
        && M.findWithDefault x y b == x
        && go (M.insert x y f) (M.insert y x b) rest

Variants to try

Check whether a sentence follows a pattern like abba, one word per letter. (It's the same two maps with words on one side in place of characters.)
Group a list of words so that the words in each group are isomorphic to each other. (Turn each word into the positions where each of its letters first appears and use that as a hash key.)

Next problems

Easy10 min

Can one word be renamed into another?

Examples

Constraints

Hints

Where people lose marks

Dry run on `"badc","baba"`

How to think about it

The solution, in six languages

Variants to try

Next problems

Pair with a given sum in an unsorted array

A repeated value within k positions

Longest run of consecutive integers

Keep going

Pair with a given sum in an unsorted array

A repeated value within k positions

Longest run of consecutive integers

The pattern behind it

Can one word be renamed into another?

Examples

Constraints

Hints

Where people lose marks

Dry run on "badc","baba"

How to think about it

The solution, in six languages

Variants to try

Next problems

Pair with a given sum in an unsorted array

A repeated value within k positions

Longest run of consecutive integers

Keep going

Pair with a given sum in an unsorted array

A repeated value within k positions

Longest run of consecutive integers

The pattern behind it

Dry run on `"badc","baba"`