Check If Two Strings Are Isomorphic

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

Solution❯

Understanding the Problem

We are given two strings, s and t, and we need to determine whether they are isomorphic.

Two strings are isomorphic if characters in one string can be replaced to get the second string — with a consistent, one-to-one mapping.

This means:

Every character in s maps to exactly one character in t.
No two characters from s map to the same character in t.

Think of this as a character-translation problem: we’re translating each character in s to a character in t. The translation must be consistent and unique.

Step-by-Step Solution with Example

Step 1: Take a simple example

Let’s consider the example: s = "egg" and t = "add"

We’ll walk through each character pair and see how the mappings work.

Step 2: Use two hash maps

We use two maps (dictionaries):

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

Step 3: Iterate through the strings

We loop through each character pair:


i = 0 → s[0] = 'e', t[0] = 'a'  
→ 'e' is not in s_to_t → map 'e' → 'a'  
→ 'a' is not in t_to_s → map 'a' → 'e'

i = 1 → s[1] = 'g', t[1] = 'd'  
→ 'g' is not in s_to_t → map 'g' → 'd'  
→ 'd' is not in t_to_s → map 'd' → 'g'

i = 2 → s[2] = 'g', t[2] = 'd'  
→ 'g' is already mapped to 'd' → OK  
→ 'd' is already mapped to 'g' → OK

All characters follow consistent one-to-one mapping. So, the strings are isomorphic.

Step 4: Check for mismatches

Let’s consider another example: s = "foo", t = "bar"


i = 0 → 'f' → 'b'  
i = 1 → 'o' → 'a'  
i = 2 → 'o' → 'r' → ❌ mismatch! 'o' was already mapped to 'a'

So we return false.

Edge Cases

Empty Strings: If both s and t are empty, they are trivially isomorphic — nothing to map, no conflict.
Different Lengths: If s.length !== t.length, they can’t be isomorphic. Each character must have a match.
Repeated Characters: Repetition is fine as long as the mapping stays consistent. For example: s = "paper", t = "title" → Valid isomorphic pair.

Finally

To solve this problem:

Understand the core rule — one-to-one and consistent character mapping.
Use two dictionaries to track both directions of mapping.
Validate that no character breaks the mapping rule during iteration.

This approach is simple, beginner-friendly, and ensures you check all logical mapping conditions.

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

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool isIsomorphic(char* s, char* t) {
    if (strlen(s) != strlen(t)) return false;

    int sToT[256] = {0};
    int tToS[256] = {0};

    for (int i = 0; s[i]; i++) {
        char sc = s[i], tc = t[i];
        if (sToT[sc] == 0 && tToS[tc] == 0) {
            sToT[sc] = tc;
            tToS[tc] = sc;
        } else if (sToT[sc] != tc || tToS[tc] != sc) {
            return false;
        }
    }
    return true;
}

int main() {
    printf("%s\n", isIsomorphic("egg", "add") ? "true" : "false");
    printf("%s\n", isIsomorphic("foo", "bar") ? "true" : "false");
    return 0;
}

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 in Two Strings

Next Topic ⮕Check String Rotation using Concatenation

Comments

Loading comments...

Isomorphic Strings - Visualization

Contents

Visualization Player

Problem Statement❯

Examples❯

Solution❯

Understanding the Problem

Step-by-Step Solution with Example

Step 1: Take a simple example

Step 2: Use two hash maps

Step 3: Iterate through the strings

Step 4: Check for mismatches

Edge Cases

Finally

Algorithm Steps❯

Code

Time Complexity❯

Space Complexity❯

Comments

Isomorphic Strings - Visualization

Contents

Visualization Player

Problem Statement❯

Examples❯

Solution❯

Understanding the Problem

Step-by-Step Solution with Example

Step 1: Take a simple example

Step 2: Use two hash maps

Step 3: Iterate through the strings

Step 4: Check for mismatches

Edge Cases

Finally

Algorithm Steps❯

Code

Time Complexity❯

Space Complexity❯

Comments

Player Settings