205 - Isomorphic Strings

Difficulty: Easy | Pattern: Hash Map | Company tags: LinkedIn, Facebook, Amazon

Problem Statement

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true  (e→a, g→d)

Example 2:

Input: s = "foo", t = "bar"
Output: false  (o→a and o→r is inconsistent)

Example 3:

Input: s = "paper", t = "title"
Output: true  (p→t, a→i, e→l, r→e)

Approach: Two Hash Maps — O(n)

Key insight: Maintain two maps: s_to_t (s char → t char) and t_to_s (t char → s char). For each character pair, check consistency in both directions. Two maps are needed to prevent many-to-one mappings.

def isIsomorphic(s: str, t: str) -> bool:
    s_to_t = {}
    t_to_s = {}
    
    for cs, ct in zip(s, t):
        if cs in s_to_t:
            if s_to_t[cs] != ct:
                return False
        else:
            if ct in t_to_s:
                return False  # ct already mapped from a different cs
            s_to_t[cs] = ct
            t_to_s[ct] = cs
    
    return True

Alternative: Index-Based — O(n)

Map each character to its last seen position. Two strings are isomorphic if their "last-seen" patterns are identical.

def isIsomorphic(s: str, t: str) -> bool:
    def transform(string):
        mapping = {}
        result = []
        for i, c in enumerate(string):
            if c not in mapping:
                mapping[c] = i
            result.append(mapping[c])
        return result
    
    return transform(s) == transform(t)

Algorithm Flow

Dry Run

s = "egg", t = "add"

i	cs	ct	s_to_t	t_to_s	valid?
0	e	a	e→a	a→e	✓
1	g	d	g→d	d→g	✓
2	g	d	g already→d, ct=d ✓		✓

True ✓

s = "foo", t = "bar"

i	cs	ct	check
0	f	b	map f→b, b→f
1	o	a	map o→a, a→o
2	o	r	s_to_t[o]=a but ct=r → False

Edge Cases

• Empty strings → True
• Single character → always True
• s = "ab", t = "aa": a→a, then b→a but a already maps to... wait: b not in s_to_t, but 'a' is in t_to_s already → False ✓

Complexity

• Time: O(n)
• Space: O(1) — at most 256 distinct ASCII characters

Key Terms

Term	Definition (in context of this problem)
Bijective mapping	Isomorphism requires a one-to-one correspondence between characters of s and t — no many-to-one mappings allowed.
Two hash maps	s_to_t and t_to_s track the forward and reverse mapping simultaneously so violations in either direction are caught immediately.
Last-seen index encoding	Alternative technique: replace each character with the index it last appeared at, turning isomorphism into an array-equality check.
Order preservation	Characters must map consistently at every position; the mapping is checked left-to-right in a single pass, not just for uniqueness.

FAQ

1. Can this be solved without extra space? Not truly O(1) in general, but since the alphabet is bounded (e.g., 256 ASCII characters), the two hash maps use O(1) space relative to input size, even though technically it's O(k) for alphabet size k.
2. What if one or both strings are empty? If both are empty, they're trivially isomorphic (return True — the loop never executes). The problem guarantees s.length == t.length, so a length mismatch isn't a case you need to handle explicitly, but production code should still check it first.
3. Why is a single hash map (s→t only) not enough? Because it doesn't prevent two different source characters from mapping to the same target character (e.g., s="ab", t="aa") — you need the reverse map t_to_s to catch that many-to-one violation.
4. What's the common follow-up interviewers ask? "Determine if two strings are isomorphic in a case-insensitive way" or "extend to check if a string follows a given pattern" (LeetCode 290, Word Pattern), which uses the exact same two-map technique on word tokens instead of characters.
5. How would this change if unicode/multi-byte characters were involved? The hash-map approach still works unchanged since Python dict keys can be any hashable character; only the fixed-size array optimization (assuming 256 ASCII slots) would need to become a hash map instead of a fixed array.

Quick Revision

• Isomorphic means a consistent one-to-one character substitution turns s into t while preserving order.
• Use two hash maps (s_to_t, t_to_s) to enforce the bijection in both directions during one pass.
• Reject as soon as s_to_t[cs] != ct or ct is already claimed by a different source character.
• Alternative: encode each string as "last-seen index per character" and compare the two encoded arrays.
• A character may map to itself (e.g., 'a'→'a'), that's still valid.
• Time is O(n) single pass; space is O(1) bounded by alphabet size.
• Classic pitfall: checking only one direction of the mapping misses many-to-one violations like s="ab", t="aa".
• Same-length input is guaranteed by the problem, but always verify in production code.

Related Problems

• 242-ValidAnagram — also uses character-frequency hash maps, though the invariant differs (multiset equality vs. bijective mapping).
• 383-RansomNote — related hash-map counting pattern over characters.
• 890-FindAndReplacePattern — same last-seen/normalized-pattern technique applied to matching words against a pattern.
• LeetCode 290 (Word Pattern) — same two-map bijection technique applied at word granularity; not in this directory.