Isomorphic Strings
Asked at Bloomberg
Problem
Isomorphic Strings asks whether the characters of s can be replaced to get t, where every occurrence of a character maps to the same replacement and no two different characters map to the same one. "egg" and "add" are isomorphic; "foo" and "bar" are not. The catch is that the mapping must be one-to-one in both directions.
Asked At
| Company | Difficulty | |
|---|---|---|
| Bloomberg | Easy | View all Bloomberg questions → |
How to Think About It
A single map from s to t is not enough. For s = "ab", t = "aa", the map a->a, b->a is consistent in one direction but two source characters share a target.
Key insight: keep two maps — s -> t and t -> s — and check both at every position. If either existing mapping disagrees with the current pair, return false.
An equivalent trick: compare the "first index" pattern. Replace each character by the index where it first appeared; "egg" becomes [0,1,1] and "add" becomes [0,1,1]. The strings are isomorphic iff their patterns match.
Walkthrough for s = "paper", t = "title": p->t, a->i, p->t (consistent), e->l, r->e. Reverse map has no conflicts -> true.
Edge cases: the strings are guaranteed equal length. Characters can be any ASCII, including digits and spaces.
Optimal Approach
Step 1: Create maps st and ts.
Step 2: For each position i with a = s[i], b = t[i]:
If a in st and st[a] != b: return false.
If b in ts and ts[b] != a: return false.
Set st[a] = b and ts[b] = a.
Step 3: Return true.
Time: O(n). Space: O(k) where k is the alphabet size.
What Trips People Up in Real Interviews
Checking only one direction. "badc" vs "baba" passes an s -> t check but fails because b and d both map to b.
Sorting or counting characters. Frequency counts cannot capture order — "ab" vs "ba" have the same counts and are isomorphic, but "aab" vs "aba" have the same counts and are not.
Assuming only lowercase letters. The input can contain any printable ASCII, so use a map (or a 256-size array), not a 26-size array.
Building the full mapping first and validating later. Checking at each step lets you exit early and keeps the code short.
Solution Code
def isIsomorphic(s, t):
st, ts = {}, {}
for a, b in zip(s, t):
if st.get(a, b) != b or ts.get(b, a) != a:
return False
st[a] = b
ts[b] = a
return TrueFrequently Asked Questions
What is the Isomorphic Strings problem?
Isomorphic Strings asks whether the characters of `s` can be replaced to get `t`, where every occurrence of a character maps to the same replacement and no two different characters map to the same one. `"egg"` and `"add"` are isomorphic; `"foo"` and `"bar"` are not. The catch is that the mapping must be one-to-one in both directions.
How do you solve Isomorphic Strings?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Isomorphic Strings?
Isomorphic Strings is asked at Bloomberg. It is a easy difficulty problem.
What are common mistakes on Isomorphic Strings?
- Checking only one direction. `"badc"` vs `"baba"` passes an `s -> t` check but fails because `b` and `d` both map to `b`.
- Sorting or counting characters. Frequency counts cannot capture order — `"ab"` vs `"ba"` have the same counts and are isomorphic, but `"aab"` vs `"aba"` have the same counts and are not.
- Assuming only lowercase letters. The input can contain any printable ASCII, so use a map (or a 256-size array), not a 26-size array.
- Building the full mapping first and validating later. Checking at each step lets you exit early and keeps the code short.