Isomorphic Strings

Problem Link

Problem Statement

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

Two strings are isomorphic if:

Characters in s can be replaced to get t.
Each character in s maps to only one character in t, and vice versa.
The order of characters must be preserved.
A character can map to itself, but no two different characters from s can map to the same character in t.

Examples

Example 1:

Input: s = "egg", t = "add"
Output: true
Explanation: 'e' → 'a', 'g' → 'd'

Example 2:

Input: s = "foo", t = "bar"
Output: false
Explanation: 'o' needs to map to both 'a' and 'r', which is invalid.

Example 3:

Input: s = "paper", t = "title"
Output: true
Explanation: 'p' → 't', 'a' → 'i', 'e' → 'l', 'r' → 'e'

Constraints

1 <= s.length <= 5 * 10⁴
s.length == t.length
s and t consist of any valid ASCII characters

Intuition

We need to check if a one-to-one mapping between characters of s and t exists and is consistent throughout the string.

A valid isomorphic mapping must satisfy both conditions:

Each character in s should map to only one character in t.
Each character in t should receive only one mapping from s.

So we need a bidirectional mapping to verify consistency in both directions.

Approach

We use two arrays (map1 and map2) of size 256 (to cover all ASCII characters), which store the last index (i + 1) at which each character was seen.

Key Insight:
Instead of using a HashMap, we compare mapping histories by checking:

If map1[s.charAt(i)] != map2[t.charAt(i)], return false (inconsistent mapping)
Otherwise, record the current index (i + 1) in both maps to establish that mapping at this position.

Using i + 1 instead of i ensures we differentiate between default value 0 (never seen before) and index 0.

Java Code

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] map1 = new int[256];  // Maps characters from s
        int[] map2 = new int[256];  // Maps characters from t

        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);

            // If previously seen indices don't match, mapping is inconsistent
            if (map1[c1] != map2[c2]) return false;

            // Set the index (i+1 to distinguish from default 0)
            map1[c1] = i + 1;
            map2[c2] = i + 1;
        }

        return true;
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	`O(n)`
Space Complexity	`O(1)`

Time: We scan the strings once.
Space: Constant space (256 sized arrays) for ASCII characters.

Dry Run

Input:

s = "paper", t = "title"

i = 0: s[i] = 'p', t[i] = 't' → map1['p'] = 1, map2['t'] = 1 ✅
i = 1: s[i] = 'a', t[i] = 'i' → map1['a'] = 2, map2['i'] = 2 ✅
i = 2: s[i] = 'p', t[i] = 't' → map1['p'] == map2['t'] == 1 ✅
i = 3: s[i] = 'e', t[i] = 'l' → map1['e'] = 4, map2['l'] = 4 ✅
i = 4: s[i] = 'r', t[i] = 'e' → map1['r'] = 5, map2['e'] = 5 ✅

All mappings are consistent → Return true

Alternate Approaches

Two HashMaps: One for s → t, one for t → s.
Slightly heavier but more intuitive if characters aren't ASCII.
Single Map + Set: Map s → t and use a Set to track used characters in t.
More error-prone as bidirectional mapping is harder to enforce.

Conclusion

This problem checks your understanding of bijective mappings (one-to-one and onto). It’s an important pattern for problems involving character correspondence, such as:

Anagram Checks
Pattern Matching
Encodings/Transformations

The optimal solution uses simple arrays to achieve O(n) time and O(1) space.