Faangprep Logo
Log inStart free
Browse curriculum

Isomorphic Strings

Check whether two strings are isomorphic with two hash maps, s to t and t to s, that must stay consistent for every pair of letters.

EasySolve on LeetCode

Problem Understanding

Isomorphic Strings: two strings s and t of the same length are isomorphic if the letters of s can be replaced to get t. Every occurrence of a letter must become the same letter, and no two letters may become the same letter (a letter may map to itself).

Example: "egg" and "add" are isomorphic (e→a, g→d). "foo" and "bar" are not: o would have to become both a and r.

The Intuition: A Mapping That Works Both Ways

Line the strings up so each index is a pair (a, b). Record each pair in a hash map and check every later pair against it.

One map is not enough. s→t stops a from becoming two different letters, but it lets two different letters both become b. So keep a second map t→s:

  1. If a is in s→t with a value other than b: clash.
  2. If b is in t→s with a value other than a: clash.
  3. Otherwise record a→b and b→a.

The same "remember what you have seen" check powers Valid Anagram and Group Anagrams.

Interactive Walkthrough

s is on the top row and t right under it, so each column is one pair. Both maps are beside the figure. Try Reverse clash to see a case where only the t → s map catches the problem.

Dry Run Table

Input: s = "badc", t = "baba"

i Pair s → t check t → s check Result
0 b, b new new record
1 a, a new new record
2 d, b new b came from b, not d clash

Answer: false. A single s → t map would have missed this.

The Solution Template

Two maps checked in both directions. The C version uses two 256-entry arrays, since the strings are ASCII.

Isomorphic Strings Code
1var isIsomorphic = function(s, t) {
2    const sToT = new Map(), tToS = new Map();
3    for (let i = 0; i < s.length; i++) {
4        const a = s[i], b = t[i];
5        if ((sToT.has(a) && sToT.get(a) !== b) || (tToS.has(b) && tToS.get(b) !== a)) return false;
6        sToT.set(a, b);
7        tToS.set(b, a);
8    }
9    return true;
10};

Edge Cases & Common Mistakes

  • Only one map: "badc" / "baba" passes an s → t check but is not isomorphic.
  • A letter mapping to itself: allowed; "ab" / "ab" is isomorphic.
  • Same letters, different structure: "ab" / "aa" fails at index 1 through the t → s map.
  • Java boxing: comparing two Character objects with != compares references; compare against a char so the value is unboxed.
  • Character set: LeetCode allows any ASCII character, so a 26-letter array is not enough; use a map or 256 entries.

Summary

Walk both strings together with two maps, s → t and t → s. Any pair that disagrees with either map means the strings are not isomorphic; otherwise record it both ways. O(n) time and O(k) space for an alphabet of size k.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Majority Element

Next

Word Pattern

The approach, step by step

  1. Walk both strings together

    Take the pair (a, b) = (s[i], t[i]) at each index.

  2. Check both directions

    If a already maps to something other than b, or b is already mapped from something other than a, return false.

  3. Record the pair

    Set s_to_t[a] = b and t_to_s[b] = a. If the loop ends, return true.

Frequently asked questions

Why do you need two hash maps for Isomorphic Strings?

One map from s to t only stops a letter of s from becoming two different letters. It does not stop two different letters of s from becoming the same letter of t. For s = "badc" and t = "baba", the s→t map is happy (b→b, a→a, d→b, c→a), but b and d both map to b. The t→s map catches it.

What does isomorphic mean for strings?

Two strings are isomorphic if you can replace letters of s consistently to get t: every occurrence of a letter maps to the same letter, and no two different letters map to the same one. In other words, the mapping is a one-to-one correspondence.

Is there a one-map alternative?

Yes. Map each string to the pattern of first-occurrence indexes, e.g. "egg" and "add" both become [0, 1, 1]. The strings are isomorphic exactly when those patterns are equal.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description