Abstract / Summary

Check if characters in one string can be replaced to get the other while keeping the mapping consistent both ways.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (4+ million submissions).

Typical patterns to solve this problem:

• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether two strings s and t are isomorphic. Two strings are isomorphic when characters in s can be replaced to obtain t while preserving the order of characters, and no two different characters from s map to the same character in t. The algorithm builds two dictionaries that record the forward mapping (s → t) and the reverse mapping (t → s). After processing all positions, it validates that the number of distinct mappings in both directions is identical, which guarantees a bijective relationship.

Key Steps

Initialization of Mapping Containers

The solution creates two empty dictionaries to store character correspondences.

s2t = {}
t2s = {}

These structures enable constant-time look-ups for previously seen characters, which is essential for detecting conflicting mappings early.

Iteration Over Characters

A single loop traverses the indices of the input strings. The loop length equals the length of s, which is assumed to be the same as t for a valid isomorphism check.

for i in range(len(s)):

Processing characters by index allows simultaneous access to the paired characters s[i] and t[i].

Forward Mapping Validation

Inside the loop, the code first checks whether the current character from s already has an entry in the forward dictionary. If it does, the stored target character must match the current character from t; otherwise the strings cannot be isomorphic and the function returns False.

if s[i] in s2t:
    if s2t[s[i]] != t[i]:
        return False
else:
    s2t[s[i]] = t[i]

This step ensures that a single source character never maps to two different target characters.

Reverse Mapping Update

Regardless of whether the forward mapping existed, the reverse dictionary is updated with the current pair. This unconditional assignment records the most recent source character for each target character.

t2s[t[i]] = s[i]

Because the forward check already guarantees consistency, overwriting an existing entry in t2s does not introduce contradictions.

Final Consistency Check

After the loop finishes, the function compares the number of distinct keys in both dictionaries. Equality of these counts confirms that the mapping is one-to-one in both directions.

return len(s2t.keys()) == len(t2s.keys())

If the counts differ, it would indicate that some target character was associated with multiple source characters, violating the isomorphism condition.

Edge Cases Handled

The algorithm gracefully handles strings containing repeated characters. When a character repeats in s, the forward dictionary already contains an entry, and the code verifies that the corresponding character in t matches the stored mapping. This prevents false positives where a repeated source character could incorrectly map to different target characters.

When t contains repeated characters, the reverse dictionary is updated each time. Because the forward validation already ensures a unique mapping from each source character, the final key-count comparison catches any scenario where two different source characters map to the same target character.

Empty strings are also covered: the loop body never executes, both dictionaries remain empty, and the final comparison yields True, correctly indicating that two empty strings are trivially isomorphic.

Performance Optimizations Observed

The solution uses two hash tables for constant-time insertion and lookup, eliminating the need for nested loops or repeated scans of the strings. By performing the forward consistency check before updating the reverse dictionary, the algorithm avoids unnecessary work when a conflict is detected early, allowing an immediate return. The final equality test on dictionary key counts is a single O(1) operation after the linear pass, avoiding any additional traversal of the strings. These choices keep the overall processing time proportional to the length of the input strings while using only a modest amount of auxiliary memory for the two dictionaries.

Imagine you have two rows of colorful building blocks and a special magic notebook. The goal is to see if these two rows are wearing the exact same patterns, even if the colors are different.

First, empty out two pages in the notebook. One page is for remembering how colors in the first row match up to colors in the second row, and the other page is for tracking the reverse.

Now, walk along the rows one step at a time. Pick up a block from the first row and a block from the second row at the same spot. Check the notebook to see if a secret code for the first color has already been written down. If it is already there, make sure it matches the new block. If it is not there, write it down so the notebook remembers the pair.

Do this for every single block in both rows. Once finished, count how many unique color rules were saved in both pages of the notebook. If the number of rules on both sides matches, it means the pattern is the same.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#		Rust		Go			TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis							JS
	fartem									Ruby
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	gouthampradhan			Java
	halfrost								Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	muhammadfarhankt								Go
	pruthvikp		Python
	qiyuangong		Python
	ruoru						Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02					C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666										Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality