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 Sam K., 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

More Hash Tables practice problems

See all Hash Tables problems →