28. Isomorphic Strings
easyAsked at DatadogDetermine if two strings are isomorphic — every character in s maps to one in t under a consistent 1-to-1 substitution. Datadog asks this for the two-way-mapping insight — same shape as their tag-name canonicalization on ingest.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Datadog loops.
- Glassdoor (2026-Q1)— Datadog phone screen string problem.
Problem
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.
Constraints
1 <= s.length <= 5 * 10^4t.length == s.lengths and t consist of any valid ASCII character.
Examples
Example 1
s = "egg", t = "add"trueExample 2
s = "foo", t = "bar"falseExample 3
s = "paper", t = "title"trueApproaches
1. One-way map (broken)
Single map s_char -> t_char. Misses the 'no two s chars map to the same t char' rule.
- Time
- O(n)
- Space
- O(1)
function isIsomorphic(s, t) {
const m = new Map();
for (let i = 0; i < s.length; i++) {
if (m.has(s[i])) { if (m.get(s[i]) !== t[i]) return false; }
else m.set(s[i], t[i]);
}
return true;
}Tradeoff: Wrong on cases like 'foo' -> 'bar' (passes incorrectly). Datadog will catch this.
2. Two-way mapping (optimal)
Track both s->t and t->s. Both must be consistent (bijection).
- Time
- O(n)
- Space
- O(1) bounded by alphabet
function isIsomorphic(s, t) {
const stMap = new Map();
const tsMap = new Map();
for (let i = 0; i < s.length; i++) {
const sc = s[i], tc = t[i];
if (stMap.has(sc) && stMap.get(sc) !== tc) return false;
if (tsMap.has(tc) && tsMap.get(tc) !== sc) return false;
stMap.set(sc, tc);
tsMap.set(tc, sc);
}
return true;
}Tradeoff: Two maps enforce bijection. Datadog-canonical — directly maps to their tag-canonicalization integrity check.
Datadog-specific tips
Datadog will probe with the 'foo' -> 'bar' counterexample to see if you spot that one-way mapping fails. Articulate the bijection requirement BEFORE coding — the two maps are non-obvious unless you've thought it through.
Common mistakes
- Single-direction map — passes 'egg'/'add' but fails 'foo'/'bar' or 'badc'/'baba'.
- Using Object.create(null) without thinking about prototype pollution — Map is the safer default.
- Comparing first-occurrence positions instead of using maps — works (encode-by-index) but allocates more.
Follow-up questions
An interviewer at Datadog may pivot to one of these next:
- Word Pattern (LC 290) — same idea but pattern is char per word.
- Group Anagrams (LC 49) — different kind of equivalence relation.
- Datadog-style: canonicalize tag IDs across two ingestion paths.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why two maps?
Isomorphism requires a BIJECTION between character sets. One map allows two distinct s-chars to map to the same t-char, violating the 1-to-1 rule.
Could you encode characters by first-occurrence index?
Yes — transform both strings into 'position of first occurrence' arrays and compare. Equivalent but allocates O(n) per string.