241. Check if Two Strings Are Isomorphic

Given two strings s1 and s2, print 'Yes' if they are isomorphic - meaning there's a one-to-one correspondence between the distinct characters of s1 and the distinct characters of s2 such that replacing every occurrence of each character of s1 with its corresponding character of s2 throughout reproduces s2 exactly (and no two different characters of s1 ever map to the same character of s2). Otherwise, or if the two strings have different lengths, print 'No'.

Input: Two lines: the first contains s1, the second contains s2. Output: Print 'Yes' if s1 and s2 are isomorphic, otherwise print 'No'.

1 <= |s1|, |s2| <= 10^5

This is fundamentally about a strict ONE-TO-ONE (bijective) correspondence between characters, not just 'some consistent replacement rule' - the two-way mapping check is precisely what distinguishes true isomorphism from a weaker, one-directional pattern match.

Check whether two strings have the same underlying character PATTERN, where each character in the first string always maps to exactly one specific character in the second (and vice versa). Brute force: Try every possible one-to-one character mapping between the two alphabets directly and check if applying it to s1 reproduces s2 exactly - this is combinatorially wasteful compared to just building the mapping incrementally as you scan. Optimised: Maintaining BOTH forward (s1->s2) and backward (s2->s1) mappings simultaneously, checked at every position in a single pass, correctly enforces the TRUE one-to-one requirement - checking only one direction would incorrectly accept cases where two different s1 characters both map to the same s2 character, which isn't a genuine isomorphism.

For every pair of indices i and j in the string, check whether s1[i] equals s1[j] exactly when s2[i] equals s2[j]; if this consistency ever breaks for any pair, the strings are not isomorphic. This directly tests the definition of isomorphism - that equal characters at any two positions in one string must correspond to equal characters at the same two positions in the other, and vice versa - but comparing every pair of positions means redoing the same character comparisons many times over. Time: O(n^2) Space: O(1)

Scan both strings together once while maintaining two hash maps: one mapping each character of s1 to the character of s2 it has been paired with so far, and another mapping each character of s2 back to its paired character of s1. At each position, if either map already has an entry for the current characters, verify it matches the current pair; otherwise insert new entries in both maps. This is correct because checking both directions ensures the mapping is a true one-to-one bijection, not just a one-way substitution, and it finishes in a single linear pass instead of the brute force's repeated pairwise comparisons. Time: O(n) Space: O(n)

Replace the two hash maps with two fixed-size arrays (sized to the character set, e.g. 256 for extended ASCII) that store the last position at which each character was seen in s1 and in s2 respectively. Scanning once, at each index compare the last-seen position recorded for s1[i] against the last-seen position recorded for s2[i]; they must match (both unseen, or both last seen at the same earlier index), then update both arrays to the current index. This preserves the same single-pass bijection check as the hash-map version but replaces hashing overhead with direct constant-time array indexing, giving effectively constant extra space since the array size is bounded by the alphabet rather than growing with the input. Time: O(n) Space: O(1)

1. If the two strings have different lengths, answer No immediately. 2. Walk through both strings simultaneously, maintaining TWO hashmaps: one mapping characters of s1 to their corresponding characters of s2, and one mapping the other direction. 3. At each position, check both mappings stay consistent: if s1's character has been mapped before, it must map to the SAME character of s2 as before (and vice versa) - any conflict means the strings aren't isomorphic.

Time: O(n) - one single pass through both strings simultaneously, with O(1) hashmap lookups at each position. Space: O(alphabet size), for the two mapping hashmaps.

Test with s1 and s2 of different lengths (immediate 'No'), strings of length 1, a case requiring a many-to-one mapping (e.g. "foo"/"bar", which must fail), and both strings at length 10^5 for performance.

Be ready to explain explicitly WHY checking only ONE direction of the mapping is insufficient - a common subtle bug is forgetting the reverse mapping check, which would wrongly accept strings like 'ab' and 'aa' as isomorphic.