Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Isomorphic Strings

EASYProblemSolveExternal Links

Description

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

Two strings are isomorphic if the characters in s can be replaced to get t, subject to the following rules:

  • Every occurrence of a character in s must be replaced with the same character in t.
  • No two different characters in s may map to the same character in t.
  • A character may map to itself.
  • The order and relative positions of characters must be preserved.

In other words, there must be a one-to-one correspondence (bijection) between the characters of s and t such that replacing each character in s by its corresponding character produces t.

Examples

Example 1

Input: s = "egg", t = "add"

Output: true

Explanation: We can map 'e' → 'a' and 'g' → 'd'. Applying this mapping to "egg" gives "add", which matches t. The mapping is one-to-one: each character in s maps to exactly one character in t, and no two characters in s share a mapping target.

Example 2

Input: s = "foo", t = "bar"

Output: false

Explanation: The character 'o' appears at positions 1 and 2 in s. At position 1, it would need to map to 'a', but at position 2, it would need to map to 'r'. Since 'o' cannot map to both 'a' and 'r', the strings are not isomorphic.

Example 3

Input: s = "paper", t = "title"

Output: true

Explanation: We can establish the mapping: 'p' → 't', 'a' → 'i', 'e' → 'l', 'r' → 'e'. Applying this to "paper": p→t, a→i, p→t, e→l, r→e gives "title". The mapping is consistent and one-to-one.

Example 4

Input: s = "badc", t = "baba"

Output: false

Explanation: Attempting a mapping: 'b' → 'b', 'a' → 'a', 'd' → 'b', 'c' → 'a'. Here 'd' maps to 'b' and 'b' also maps to 'b'. Two different characters ('b' and 'd') map to the same target 'b', violating the one-to-one requirement. The strings are not isomorphic.

Constraints

  • 1 ≤ s.length ≤ 5 × 10^4
  • t.length == s.length
  • s and t consist of any valid ASCII character.

Editorial

Brute Force

Intuition

The most straightforward way to check if two strings are isomorphic is to verify the consistency rule directly: for every pair of positions (i, j) in the strings, the relationship between characters must be preserved.

Specifically, if s[i] == s[j], then t[i] must equal t[j] (same character in s maps to same character in t). Conversely, if s[i] != s[j], then t[i] must not equal t[j] (different characters in s must map to different characters in t).

Think of it like a substitution cipher. If the letter 'A' is encrypted as 'X' in one place, it must be encrypted as 'X' everywhere. And if 'B' is a different letter from 'A', it must encrypt to something different from 'X'. We check every pair of positions to ensure these rules hold.

Step-by-Step Explanation

Let's trace through with s = "foo", t = "bar".

We check every pair of positions (i, j) where i < j.

Step 1: Compare positions (0, 1).

  • s[0] = 'f', s[1] = 'o'. Are they the same? No.
  • t[0] = 'b', t[1] = 'a'. Are they the same? No.
  • Consistent ✓ (different maps to different).

Step 2: Compare positions (0, 2).

  • s[0] = 'f', s[2] = 'o'. Same? No.
  • t[0] = 'b', t[2] = 'r'. Same? No.
  • Consistent ✓.

Step 3: Compare positions (1, 2).

  • s[1] = 'o', s[2] = 'o'. Same? YES.
  • t[1] = 'a', t[2] = 'r'. Same? NO.
  • INCONSISTENT ✗! The same character 'o' in s maps to two different characters ('a' and 'r') in t. This violates the one-to-one rule.

Result: Return false.

Brute Force — Check All Position Pairs — Watch how we compare every pair of positions to verify that the character relationship is consistent between s and t.

Algorithm

  1. For each pair of indices (i, j) where 0 ≤ i < j < n:
    a. Check if (s[i] == s[j]) implies (t[i] == t[j]) — same char in s → same char in t.
    b. Check if (t[i] == t[j]) implies (s[i] == s[j]) — same char in t → same char in s.
    c. If either check fails, return false.
  2. If all pairs are consistent, return true.

Code

#include <string>
using namespace std;

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int n = s.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // If same char in s, must be same char in t
                if (s[i] == s[j] && t[i] != t[j]) return false;
                // If same char in t, must be same char in s
                if (t[i] == t[j] && s[i] != s[j]) return false;
            }
        }
        
        return true;
    }
};
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        n = len(s)
        
        for i in range(n):
            for j in range(i + 1, n):
                # If same char in s, must be same char in t
                if s[i] == s[j] and t[i] != t[j]:
                    return False
                # If same char in t, must be same char in s
                if t[i] == t[j] and s[i] != s[j]:
                    return False
        
        return True
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // If same char in s, must be same char in t
                if (s.charAt(i) == s.charAt(j) && t.charAt(i) != t.charAt(j))
                    return false;
                // If same char in t, must be same char in s
                if (t.charAt(i) == t.charAt(j) && s.charAt(i) != s.charAt(j))
                    return false;
            }
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n²)

We check all pairs of positions. There are n × (n-1) / 2 pairs, each requiring constant-time comparisons. With n up to 5 × 10^4, this is about 1.25 × 10^9 operations — too slow for typical time limits.

Space Complexity: O(1)

No additional data structures are used beyond loop variables.

Why This Approach Is Not Efficient

The brute force checks all O(n²) pairs. With n up to 50,000, this gives ~1.25 billion comparisons — beyond acceptable time limits.

The core inefficiency is that we keep re-examining the same character relationships. When we see 'o' at position 1 and later see 'o' at position 2, we compare them. If we see 'o' again at position 5, we'd compare it with both positions 1 and 2 again.

Instead of comparing every pair, we can remember the mapping as we go. When we first see 'o' in s paired with 'a' in t, we record: "'o' maps to 'a'". When we see 'o' again later, we just check: "does our recorded mapping match?" This is exactly what a hash map does — store and look up key-value pairs in O(1) time.

We need two hash maps — one for s → t and one for t → s — because the mapping must be bidirectional (one-to-one). Checking only one direction would miss cases where two different characters in s try to map to the same character in t.

Optimal Approach - Two Hash Maps

Intuition

Instead of checking all pairs of positions, we build a character-to-character mapping as we scan both strings simultaneously.

Imagine you're a codebreaker deciphering a substitution cipher. You have two messages side by side — the encrypted one (s) and the decrypted one (t). As you read each position:

  1. You see a character a in the encrypted message and b in the decrypted one.
  2. You check your codebook: "Have I seen a before?" If yes, the codebook must say a → b. If it says a → c (some different character), the cipher is broken.
  3. You also check the reverse codebook: "Has b been assigned before?" If yes, it must be assigned to a. If some other character maps to b, the cipher is broken.
  4. If both checks pass, you record a → b in the forward codebook and b → a in the reverse codebook.

This ensures a bijective (one-to-one and onto) mapping. We need both directions because:

  • Forward map alone misses: s="ab", t="aa" — 'a'→'a' and 'b'→'a' passes forward check but is invalid (two chars map to same target).
  • Reverse map catches this: when we try to map 'b'→'a', the reverse map already has 'a'→'a', and 'a' ≠ 'b', so we detect the conflict.

Step-by-Step Explanation

Let's trace through with s = "paper", t = "title".

Initialize two empty maps: s_to_t = {}, t_to_s = {}.

Step 1: Position 0: s[0]='p', t[0]='t'.

  • Is 'p' in s_to_t? No.
  • Is 't' in t_to_s? No.
  • Record: s_to_t['p'] = 't', t_to_s['t'] = 'p'.
  • Maps: s_to_t = {'p':'t'}, t_to_s = {'t':'p'}.

Step 2: Position 1: s[1]='a', t[1]='i'.

  • Is 'a' in s_to_t? No.
  • Is 'i' in t_to_s? No.
  • Record: s_to_t['a'] = 'i', t_to_s['i'] = 'a'.
  • Maps: s_to_t = {'p':'t', 'a':'i'}, t_to_s = {'t':'p', 'i':'a'}.

Step 3: Position 2: s[2]='p', t[2]='t'.

  • Is 'p' in s_to_t? Yes, and s_to_t['p'] = 't'. Does 't' == 't'? YES ✓.
  • Is 't' in t_to_s? Yes, and t_to_s['t'] = 'p'. Does 'p' == 'p'? YES ✓.
  • Mapping consistent. No update needed.

Step 4: Position 3: s[3]='e', t[3]='l'.

  • Is 'e' in s_to_t? No.
  • Is 'l' in t_to_s? No.
  • Record: s_to_t['e'] = 'l', t_to_s['l'] = 'e'.

Step 5: Position 4: s[4]='r', t[4]='e'.

  • Is 'r' in s_to_t? No.
  • Is 'e' in t_to_s? No.
  • Record: s_to_t['r'] = 'e', t_to_s['e'] = 'r'.

Step 6: All positions processed without conflict.

Result: Return true. The mapping p→t, a→i, e→l, r→e is a valid bijection.

Two Hash Maps — Building Bidirectional Mapping — Watch how we simultaneously build forward (s→t) and reverse (t→s) mappings, checking for conflicts at each position.

Now let's trace a failure case: s = "foo", t = "bar".

Two Hash Maps — Conflict Detection on "foo" / "bar" — Watch how the forward map catches a conflict when the same character in s tries to map to two different characters in t.

Algorithm

  1. Create two empty hash maps: s_to_t (forward mapping) and t_to_s (reverse mapping).
  2. Iterate through both strings simultaneously (same index i):
    a. Let a = s[i] and b = t[i].
    b. If a is already in s_to_t and s_to_t[a] ≠ b, return false (forward conflict).
    c. If b is already in t_to_s and t_to_s[b] ≠ a, return false (reverse conflict).
    d. Record s_to_t[a] = b and t_to_s[b] = a.
  3. If the loop completes without conflicts, return true.

Code

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> s_to_t;
        unordered_map<char, char> t_to_s;
        
        for (int i = 0; i < s.size(); i++) {
            char a = s[i], b = t[i];
            
            // Check forward mapping
            if (s_to_t.count(a) && s_to_t[a] != b) return false;
            // Check reverse mapping
            if (t_to_s.count(b) && t_to_s[b] != a) return false;
            
            s_to_t[a] = b;
            t_to_s[b] = a;
        }
        
        return true;
    }
};
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_to_t = {}
        t_to_s = {}
        
        for a, b in zip(s, t):
            # Check forward mapping: a must always map to the same b
            if a in s_to_t and s_to_t[a] != b:
                return False
            # Check reverse mapping: b must always come from the same a
            if b in t_to_s and t_to_s[b] != a:
                return False
            
            s_to_t[a] = b
            t_to_s[b] = a
        
        return True
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> sToT = new HashMap<>();
        Map<Character, Character> tToS = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            char b = t.charAt(i);
            
            // Check forward mapping
            if (sToT.containsKey(a) && sToT.get(a) != b) return false;
            // Check reverse mapping
            if (tToS.containsKey(b) && tToS.get(b) != a) return false;
            
            sToT.put(a, b);
            tToS.put(b, a);
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse both strings once. At each position, we perform hash map lookups and insertions, each taking O(1) amortized time. Total: n iterations × O(1) work = O(n).

Space Complexity: O(C)

Where C is the size of the character set. Each hash map stores at most one entry per unique character. For ASCII, C ≤ 256, so the space is bounded by O(256) = O(1) in terms of input size. In the worst case with arbitrary character sets, it is O(min(n, C)).