Check if two given strings are isomorphic to each other

Problem Statement

Two strings are isomorphic if there is a one-to-one mapping between characters of the first string to characters of the second string such that each character can be replaced to get the second string.

Constraints:

• Each character maps to exactly one character (bijective mapping)
• No two characters can map to the same character
• A character can map to itself

Example:

• Input: s1 = "egg", s2 = "add"
• Output: true
• Explanation: e → a, g → d

Example 2:

• Input: s1 = "foo", s2 = "bar"
• Output: false
• Explanation: 'o' appears twice but 'a' and 'r' are different

Approach 1: Brute Force (Check All Mappings)

Intuition

For each character in s1, find its corresponding character in s2 and verify the mapping is consistent throughout.

Algorithm

1. If lengths differ, return false
2. Create mapping from s1 chars to s2 chars
3. Also track which s2 chars are already mapped (to ensure one-to-one)
4. For each position, verify mapping consistency

import java.util.*;

public class Solution {
    public boolean areIsomorphic(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        
        Map<Character, Character> mapping = new HashMap<>();
        Set<Character> mappedTo = new HashSet<>();
        
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i), c2 = s2.charAt(i);
            
            if (mapping.containsKey(c1)) {
                if (mapping.get(c1) != c2) {
                    return false;
                }
            } else {
                if (mappedTo.contains(c2)) {
                    return false;
                }
                mapping.put(c1, c2);
                mappedTo.add(c2);
            }
        }
        
        return true;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through both strings
• Space Complexity: O(n) - For storing mappings (at most 256 for ASCII)

Approach 2: Using Two HashMaps (Bidirectional Mapping)

Intuition

Maintain mappings in both directions to ensure the bijection property.

import java.util.*;

public class Solution {
    public boolean areIsomorphic(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        
        Map<Character, Character> s1ToS2 = new HashMap<>();
        Map<Character, Character> s2ToS1 = new HashMap<>();
        
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i), c2 = s2.charAt(i);
            
            if (s1ToS2.containsKey(c1) && s1ToS2.get(c1) != c2) {
                return false;
            }
            if (s2ToS1.containsKey(c2) && s2ToS1.get(c2) != c1) {
                return false;
            }
            
            s1ToS2.put(c1, c2);
            s2ToS1.put(c2, c1);
        }
        
        return true;
    }
}

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) - At most 256 entries for ASCII

Approach 3: Using Character Position Arrays (Optimal)

Intuition

Track the last position where each character was seen. If two strings are isomorphic, the pattern of positions should match.

public class Solution {
    public boolean areIsomorphic(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        
        int[] lastPos1 = new int[256];
        int[] lastPos2 = new int[256];
        
        // Initialize with -1 (never seen)
        java.util.Arrays.fill(lastPos1, -1);
        java.util.Arrays.fill(lastPos2, -1);
        
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i), c2 = s2.charAt(i);
            
            if (lastPos1[c1] != lastPos2[c2]) {
                return false;
            }
            
            lastPos1[c1] = i;
            lastPos2[c2] = i;
        }
        
        return true;
    }
}

Why Position Tracking Works

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(1) - Fixed-size arrays for ASCII

Approach 4: Transform to Canonical Form

Intuition

Transform both strings to a canonical form where the first occurrence of each character is replaced by its index of first appearance. Isomorphic strings will have the same canonical form.

Example

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n) for canonical form

Key Takeaways

1. Isomorphism is bidirectional - Both s1→s2 and s2→s1 must be consistent
2. Position tracking is an elegant O(1) space (for fixed alphabet) solution
3. Canonical form is useful for grouping isomorphic strings
4. This is LeetCode 205 - Isomorphic Strings
5. Related problems: Word Pattern, Find and Replace Pattern
6. The mapping must be a bijection (one-to-one and onto)