DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Isomorphic Strings

easyArrays and hashing

Problem statement

You are given two strings s and t of the same length. They are isomorphic if you can turn s into t by replacing characters, where:

  • every occurrence of a character is replaced by the same character,
  • two different characters never map to the same character,
  • a character may map to itself.

Return true if s and t are isomorphic, otherwise false. The strings can contain any printable ASCII characters.

Examples

Example 1

Input: s = "hello", t = "jummo"

Output: true

Explanation: h -> j, e -> u, l -> m, o -> o. Both ls become m.

Example 2

Input: s = "abca", t = "zyxw"

Output: false

Explanation: a would have to map to z at index 0 and to w at index 3.

Hints

Approach

Walk both strings together and keep two maps: s_to_t for the forward mapping and t_to_s for the reverse. The forward map enforces "same character, same replacement". The reverse map enforces "no two characters share a replacement".

  1. For each pair (a, b) at the same index:
  2. If a is already mapped to something other than b, return false.
  3. If b is already mapped back to something other than a, return false.
  4. Record a -> b and b -> a.
  5. Return true after the loop.

k is the size of the character set. For ASCII it is at most 128, so the maps are effectively constant size.

ComplexityTime O(n)Space O(k)
Python
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_to_t, t_to_s = {}, {}
for a, b in zip(s, t):
if s_to_t.get(a, b) != b or t_to_s.get(b, a) != a:
return False
s_to_t[a] = b
t_to_s[b] = a
return True

Follow-up questions

  • Given a pattern like "abba" and a sentence like "web db db web", check whether the words follow the pattern.
  • Group a list of strings so that isomorphic strings end up together.

Frequently asked questions

The forward map alone accepts s = "ab", t = "aa": a -> a and b -> a are each consistent, but two characters now share one replacement. The reverse map catches that.

Yes. Replace each character by the index of its first occurrence, so "hello" becomes [0, 1, 2, 2, 4]. Two strings are isomorphic exactly when those lists are equal. It is a neat way to explain the idea of a shared pattern.

Renaming schemes are the usual case: mapping old hostnames or volume IDs to new ones during a migration. The mapping must be consistent and must never send two old names to the same new name, which is exactly the two-map check.