Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Isomorphic Strings

Isomorphic Strings

Master this topic with zero to advance depth.

Isomorphic Strings

Two strings s and t are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Visual Representation

s = "egg", t = "add" e -> a g -> d Result: "add" (True) s = "foo", t = "bar" f -> b o -> a o -> r (Conflict! 'o' already mapped to 'a')
Easy

Examples

Input: s = "egg", t = "add"
Output: true
Input: s = "foo", t = "bar"
Output: false
Approach 1

Level I: Two HashMaps (Bidirectional)

Intuition

A character in s must map to exactly one character in t, and vice versa. We use two maps to ensure this 1-to-1 relationship.

⏱ O(N)💾 O(1) - alphabet size is finite.

Detailed Dry Run

s="ab", t="aa" m1: {a: a}, m2: {a: a} m1: {b: a}, m2 already has {a: a}! Conflict.

java
import java.util.*;
class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> m1 = new HashMap<>(), m2 = new HashMap<>();
        for(int i=0; i<s.length(); i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if((m1.containsKey(c1) && m1.get(c1) != c2) || 
               (m2.containsKey(c2) && m2.get(c2) != c1)) return false;
            m1.put(c1, c2); m2.put(c2, c1);
        }
        return true;
    }
}
Approach 2

Level II: Last Seen Index (Space Optimized)

Intuition

Characters are isomorphic if they appear at the same relative indices throughout the string. We track the 'last seen' index for each character.

⏱ O(N)💾 O(1) - fixed size arrays.

Detailed Dry Run

s="egg", t="add" e(0), a(0) -> Match g(1), d(1) -> Match g(2), d(2) -> Match

java
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256], m2 = new int[256];
        for(int i=0; i<s.length(); i++) {
            if(m1[s.charAt(i)] != m2[t.charAt(i)]) return false;
            m1[s.charAt(i)] = i + 1; m2[t.charAt(i)] = i + 1;
        }
        return true;
    }
}
Approach 3

Level III: Optimal Solution (Canonical Form)

Intuition

Convert both strings to a 'canonical' or 'normal' form where each character is replaced by the index of its first appearance. If both strings produce the same normalized form, they are isomorphic.

⏱ O(N)💾 O(N)

Detailed Dry Run

s = "paper" -> First seen indices: p:0, a:1, e:3, r:4. Normalized: [0, 1, 0, 3, 4] t = "title" -> First seen indices: t:0, i:1, l:3, e:4. Normalized: [0, 1, 0, 3, 4] Match!

java
class Solution {
    public boolean isIsomorphic(String s, String t) {
        return transform(s).equals(transform(t));
    }
    private String transform(String s) {
        Map<Character, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) map.put(s.charAt(i), i);
            sb.append(map.get(s.charAt(i))).append(",");
        }
        return sb.toString();
    }
}
← Previous QuestionBrick Wall
Next Question →Continuous Subarray Sum