Isomorphic Strings

Problem Statement❯

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t. The replacement must be consistent — every character in s must map to exactly one character in t, and no two characters from s can map to the same character in t.

The character mapping should be one-to-one and should preserve the order of characters. Return true if the strings are isomorphic, otherwise return false.

Examples❯

s	t	Output	Description
"egg"	"add"	true	'e' → 'a', 'g' → 'd' — consistent mapping
"foo"	"bar"	false	'o' maps to two different characters, which breaks the rule
"paper"	"title"	true	'p' → 't', 'a' → 'i', 'e' → 'l', 'r' → 'e'
"ab"	"aa"	false	'a' → 'a' and 'b' → 'a' — two characters from 's' map to same char in 't'
"abc"	"def"	true	Each character maps uniquely and consistently
""	""	true	Both strings are empty — trivially isomorphic
""	"abc"	false	One string is empty, the other is not
"abc"	""	false	One string is empty, the other is not
"abca"	"zbxz"	true	'a' → 'z', 'b' → 'b', 'c' → 'x' — all mappings valid
"abca"	"zbxy"	false	'a' maps to both 'z' and 'y' — mapping is inconsistent

Visualization Player

Solution❯

To check whether two strings are isomorphic, we need to understand whether we can map each character in the first string to a unique character in the second string — and do so consistently throughout the entire string.

Imagine we are translating every character from s to t. If 'a' in s maps to 'x' in t, then every time we see 'a' in s, it must be translated to 'x'. If we see 'a' later mapping to a different character (like 'y'), the strings are not isomorphic.

We also need to make sure that no two different characters in s map to the same character in t. For example, if both 'a' and 'b' map to 'x', that breaks the one-to-one requirement.

To implement this, we can use two hash maps (or dictionaries):

s_to_t: Maps characters from s to t.
t_to_s: Maps characters from t to s.

As we iterate through the characters of both strings, we:

Check if the current character from s has already been mapped to something in t. If it has, and the mapping doesn't match the current character in t, we return false.
Similarly, we check that the character in t hasn't already been assigned to a different character from s.

If we finish the loop and all mappings are valid, we return true.

Special Cases to Consider:

Empty strings: Two empty strings are trivially isomorphic — no characters means no conflicts.
Different lengths: If the strings are of unequal length, they can never be isomorphic, because we can't map characters one-to-one.
Repeated characters: It's okay if a character appears multiple times — as long as it always maps to the same character in the other string, and no conflicts arise.

This explanation focuses on helping beginners reason through character mapping with clarity before worrying about code or efficiency.

Algorithm Steps❯

Initialize two HashMaps: s_to_t and t_to_s.
Loop through each character in both strings.
For each character pair (sc, tc) from s and t:

If sc is mapped in s_to_t, it must map to tc.
If tc is mapped in t_to_s, it must map to sc.

If any mismatch is found, return false.
After the loop, return true.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def is_isomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    s_to_t = {}
    t_to_s = {}

    for sc, tc in zip(s, t):
        if sc in s_to_t:
            if s_to_t[sc] != tc:
                return False
        else:
            s_to_t[sc] = tc

        if tc in t_to_s:
            if t_to_s[tc] != sc:
                return False
        else:
            t_to_s[tc] = sc

    return True

# Example Usage
print(is_isomorphic("egg", "add"))  # True
print(is_isomorphic("foo", "bar"))  # False

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n)	We traverse both strings once, checking and updating maps in constant time.
Average Case	O(n)	Each character mapping takes constant time; total work is proportional to string length.
Worst Case	O(n)	In the worst case, every character in both strings is unique and requires a mapping.

Space Complexity❯

O(n)

Explanation: Two hash maps are used that at most store all unique characters of the strings.

⬅ Previous TopicFind Longest Common Substring

Next Topic ⮕Check String Rotation using Concatenation - Optimal Approach