Skip to main content

205. Isomorphic Strings

easy

Two strings are isomorphic if characters in one can be replaced to produce the other with a consistent one-to-one mapping. The catch most candidates miss: you need TWO maps to block both 'one source -> many targets' and 'many sources -> one target'.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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^4
  • t.length == s.length
  • s and t consist of any valid ascii character.

Examples

Example 1

Input
s = 'egg', t = 'add'
Output
true

Example 2

Input
s = 'foo', t = 'bar'
Output
false

Example 3

Input
s = 'paper', t = 'title'
Output
true

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

One hash map mapping s[i] -> t[i] isn't enough. Why? 'badc' and 'baba' would pass with just one map.

Hint 2

You need TWO maps: s_to_t and t_to_s. On each index, both must either be unset (set them) or agree (continue). Disagree -> return false.

Hint 3

Equivalent slick check: zip(s, t) walks the pairs once; reject if either map has a conflict.

Solution approach

Reveal approach

Maintain two hash maps: s_to_t and t_to_s. Walk indices 0..n-1. At each i, let a = s[i], b = t[i]. If a is in s_to_t but s_to_t[a] != b, return false. If b is in t_to_s but t_to_s[b] != a, return false. Otherwise set s_to_t[a] = b and t_to_s[b] = a. After the loop, return true. The two-map structure enforces a true bijection: s_to_t prevents 'one source -> many targets'; t_to_s prevents 'many sources -> one target'. A common bug is to use only s_to_t, which accepts 'badc' vs 'baba' incorrectly. O(n) time, O(1) space (bounded by character set).

Complexity

Time
O(n)
Space
O(1) — bounded by alphabet

Related patterns

  • hash-table
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • LinkedIn
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Isomorphic Strings and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →