#205 Isomorphic Strings
the problem
In plain words
Two strings of the same length are isomorphic if you can turn s into t by replacing characters: every occurrence of a character must become the same character, and no two different characters may become the same one. A character may stay itself. Return whether s and t are isomorphic.
in s = "egg", t = "add"
out true
e → a and g → d.
in s = "foo", t = "bar"
out false
o would have to become both a and r.
in s = "paper", t = "title"
out true
- 1 ≤ s.length ≤ 5·10⁴
- t.length == s.length
- s and t contain any valid ASCII characters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternHash lookup (seen before?)Group by a canonical key
The replacement must work in both directions — a one-to-one pairing. A map s → t catches "o becomes two letters"; only a second map t → s catches "two letters become the same one".
solutions
From brute force to optimal
Positions i and j must be equal in s exactly when they are equal in t.
- For every i and every j < i: compare s[i] == s[j] with t[i] == t[j].
- Any mismatch → false.
n(n − 1)/2 position pairs: over 10⁹ at n = 5·10⁴.
Two booleans.
class Solution { public boolean isIsomorphic(String s, String t) { for (int i = 0; i < s.length(); i++) { for (int j = 0; j < i; j++) { boolean sameInS = s.charAt(i) == s.charAt(j); boolean sameInT = t.charAt(i) == t.charAt(j); if (sameInS != sameInT) return false; // equal in one string, different in the other } } return true; }}Record s → t and t → s; put returns the previous mapping, so a conflict shows up at once.
- oldB = sToT.put(a, b); oldA = tToS.put(b, a).
- If oldB exists and isn't b, or oldA exists and isn't a → false.
- Return true.
Two O(1)-average map operations per position.
At most 128 ASCII keys per map — but every entry is boxed.
class Solution { public boolean isIsomorphic(String s, String t) { Map<Character, Character> sToT = new HashMap<>(), tToS = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char a = s.charAt(i), b = t.charAt(i); Character oldB = sToT.put(a, b); // put returns the previous mapping (or null) Character oldA = tToS.put(b, a); if (oldB != null && oldB != b) return false; // a already meant another letter if (oldA != null && oldA != a) return false; // b is already the image of another letter } return true; }}Characters are small numbers, so arrays indexed by the character replace both maps.
- sToT[a], tToS[b] store char + 1 (0 = not paired yet).
- Both free → pair a with b.
- Otherwise both entries must point at this exact pair, else false.
Constant array work per position.
Two fixed arrays of 256 ints.
class Solution { public boolean isIsomorphic(String s, String t) { int[] sToT = new int[256], tToS = new int[256]; // char + 1; 0 means "not mapped yet" for (int i = 0; i < s.length(); i++) { char a = s.charAt(i), b = t.charAt(i); if (sToT[a] == 0 && tToS[b] == 0) { // both free: pair them up sToT[a] = b + 1; tToS[b] = a + 1; } else if (sToT[a] != b + 1 || tToS[b] != a + 1) { return false; // breaks an earlier pairing } } return true; }}in the room
How to say it in the interview
talk track
- Clarify the one-to-one rule with "badc" vs "baba": b and d would both become b, so the answer is false.
- Code one map, show that counterexample passing, then add the reverse map — interviewers like seeing you test your own idea.
- Mention the arrays: with ASCII input, a 256-slot table beats a HashMap.
traps
- Checking only s → t: "badc" vs "baba" passes wrongly.
- Comparing two boxed
Charactervalues with!=compares objects; it only happens to work for cached values (0–127). Comparechars.
what they ask next
Follow-ups
Word Pattern (LC 290)?
The same two-way pairing, between pattern letters and whole words. It's the next problem.
Group many strings by their "shape"?
Turn each string into the first-occurrence position of each character ("egg" → [0,1,1], "add" → [0,1,1]) and use that as a canonical key in a HashMap.
before you submit
Edge cases to test
- One character each → true.
- "badc" vs "baba" → false: only the reverse map catches it.
- Digits, spaces and symbols are characters too ("13" vs "42" → true).
practise next
Similar problems
- #290Word PatternEasyin Hashing
- #49Group AnagramsMediumin Arrays & Strings