Isomorphic Strings

EasyHash Tables · Bijection🧩 Hashing & Counting LeetCode #205 ↗Updated Oct 30, 2026

Problem

Two equal-length strings s and t are isomorphic if you can rename the characters of s to obtain t, where each character is always renamed the same way and no two different characters receive the same new name (a character may map to itself). Return whether s and t are isomorphic.

Inputs="egg", t="add"Outputtrue

Inputs="foo", t="bar"Outputfalse

Inputs="badc", t="baba"Outputfalse

1 ≤ n ≤ 5·10⁴ · t.length == s.length · any valid ASCII characters

Try it yourself

Java

class Solution {
    public boolean isIsomorphic(String s, String t) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The mapping must be a bijection: check consistency in both directions (s→t and t→s). Equivalently, at every index the two characters must have been last seen at the same position.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceCompare Every Pair of Indices

Time O(n²)Space O(1)

A valid renaming exists iff for every pair i < j, s[i]==s[j] exactly when t[i]==t[j]. Check all pairs; any mismatch means one char maps to two, or two chars map to one.

Java

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < i; j++) {
            boolean sameS = s.charAt(i) == s.charAt(j);
            boolean sameT = t.charAt(i) == t.charAt(j);
            if (sameS != sameT) return false;
        }
    }
    return true;
}

No extra memory and easy to argue, but quadratic.

BetterTwo Hash Maps (s→t and t→s)

Time O(n)Space O(k)

Record the first mapping seen for each char in mapST and, to forbid two chars sharing a target, the reverse in mapTS. Any conflict in either map means no bijection. k = distinct characters (≤ 128).

Java

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    Map<Character, Character> mapST = new HashMap<>();
    Map<Character, Character> mapTS = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        Character prevB = mapST.putIfAbsent(a, b);
        Character prevA = mapTS.putIfAbsent(b, a);
        if ((prevB != null && prevB != b) || (prevA != null && prevA != a)) {
            return false;
        }
    }
    return true;
}

Linear and general, but boxing/hashing adds constant-factor overhead.

OptimalLast-Seen Index Arrays

Time O(n)Space O(1)

Store, for each character, the last index (+1) where it appeared. If s[i] and t[i] are a consistent pair, they were last seen together, so lastS[s[i]] == lastT[t[i]]. Storing i+1 keeps 0 meaning “never seen”.

Java

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] lastS = new int[256];
    int[] lastT = new int[256];
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        if (lastS[a] != lastT[b]) return false;
        lastS[a] = i + 1;   // +1 so 0 means "unseen"
        lastT[b] = i + 1;
    }
    return true;
}

Dry runs="paper", t="title" (cells show s/t pair)

i current index changed

i=0
p/t
i
a/i

p/t

e/l

r/e

0==0, set both=1
i=1
p/t

a/i
i
p/t

e/l

r/e

0==0, set both=2
i=2
p/t

a/i

p/t
i
e/l

r/e

p:1 == t:1 ✔
i=4
p/t

a/i

p/t

e/l

r/e
i
r:0 == e:0 → true

Single pass with two fixed 256-int arrays — fastest in practice.

At a glance

Level	Approach	Time	Space
Brute Force	Compare Every Pair of Indices	`O(n²)`	`O(1)`
Better	Two Hash Maps (s→t and t→s)	`O(n)`	`O(k)`
Optimal	Last-Seen Index Arrays	`O(n)`	`O(1)`

Common pitfalls

Checking only s→t: "ab"/"aa" would wrongly pass.
Storing i instead of i+1 — index 0 is confused with “unseen”.
Sizing arrays to 26 — the input can be any ASCII character, not just lowercase.

Interview tips

Say the word bijection early: one-to-one in both directions.
Test "badc"/"baba": each one-way map looks fine, the reverse catches it.
Note the trick generalises to Word Pattern (290) by mapping words instead of chars.

Pattern

Two-way character mapping → verify a consistent one-to-one renaming between sequences.

My notes saved in this browser