Arrays & Hashing · 165Easy
Isomorphic Strings
Two strings s and t are isomorphic if the characters in s can be replaced to get t. Every occurrence of a character must be replaced with the same character, preserving order. No two characters may map to the same character, but a character may map to itself. Return true if s and t are isomorphic.
Constraints
- 1 <= s.length <= 5 * 10^4
- t.length == s.length
- s and t consist of any valid ASCII characters.
Examples
isIsomorphic("egg", "add") -> true
isIsomorphic("foo", "bar") -> false // 'o' would need to map to both 'a' and 'r'
isIsomorphic("paper", "title") -> true
isIsomorphic("a", "b") -> true // shortest possible input
isIsomorphic("badc", "baba") -> false // 'd' and 'c' would both map to 'b'/'a' collisions
isIsomorphic("13:00", "24:11") -> true // digits and punctuation are fineEdge cases
- The mapping must be one-to-one in BOTH directions: "badc" / "baba" is false.
- Characters are not limited to letters (digits, spaces, punctuation).
Show the target complexity (spoiler)
- Naive
- O(n^2) time — for each pair of positions, check that equal-in-s means equal-in-t.
- Target
- O(n) time, O(1) space (bounded alphabet) — two maps, s -> t and t -> s, checked on every step.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/165-isomorphic-strings.js ./practice c 165