Isomorphic Strings

This question tests one idea. Can you tell if two strings share the same shape? Not the same letters. The same pattern. If you can replace the letters of one string and get the other, they match. The trick is making the replacement rule consistent.

🎯 The Problem

You decide if two strings share the same shape, not the same letters.

• The two strings have the same length.
• They are isomorphic when you can swap each letter of the first for a letter of the second in a steady, one-to-one way.
• One-to-one means each letter maps to exactly one partner. No two letters share the same partner.

For "egg" and "add": map e to a and g to d. Every e becomes a, every g becomes d. The result is "add". So they are isomorphic. The answer is true.

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

Explanation: e maps to a, g maps to d, steadily for every position.

For "foo" and "bar": f maps to b, but then o would need to map to both a and r. That breaks the one-to-one rule. So the answer is false.

Here is the problem drawn out. We line up the two strings and check the mapping at each spot.

🐢 Approach 1: Compare Patterns (Brute Force)

The idea in one line: turn each string into a number pattern, then compare the two patterns.

The idea:

• A pattern replaces each letter with the position where it first appeared.
• So "egg" becomes 0 1 1. The e is new at slot 0, g is new at slot 1, then g repeats.
• "add" also becomes 0 1 1. The patterns match, so the strings are isomorphic.

Why it is weak:

• To build a pattern, each letter scans back to find where it first showed up.
• That scan back is a second loop inside the first.
• So building each pattern costs about n times n. That is O(n²).

Here is the pattern-building code for that idea:

def pattern(word):
    seen = {}
    result = []
    for ch in word:
        if ch not in seen:
            seen[ch] = len(seen)
        result.append(seen[ch])
    return result


def is_isomorphic(s, t):
    return pattern(s) == pattern(t)

⚡ Approach 2: Two Hash Maps (Best)

The idea in one line: walk both strings together and guard the mapping in both directions with two maps.

The idea:

• A hash map stores a key and a value and looks them up almost instantly.
• One map remembers what each letter of the first string maps to.
• The other remembers what each letter of the second string maps to.

Why two maps:

• The first map stops one first-string letter from pointing at two partners.
• The second map stops two first-string letters from sharing one partner.
• Both rules must hold for a true one-to-one mapping.

How it works:

• At each position, look at the pair of letters.
• If the first letter was seen before, its stored partner must match the current second letter, or it is a conflict.
• Do the same check the other way with the second map.
• If both pass, record the mapping in both maps and move on.

Why it is fast:

• One pass through the strings. Each map check is almost instant. So O(n).

Here is the dry run on "foo" and "bar" where the conflict shows up.

Steps to Solve

1. If the two strings are different lengths, return false right away.
2. Create two empty hash maps, one for each direction.
3. Walk both strings together, one position at a time.
4. Look at the letter from the first string and the letter from the second string.
5. If the first letter is already mapped, its partner must equal the current second letter, or return false.
6. If the second letter is already mapped, its partner must equal the current first letter, or return false.
7. If no conflict, record both directions in the two maps.
8. If you reach the end with no conflict, return true.

#include <stdio.h>
#include <string.h>

int isIsomorphic(const char *s, const char *t) {
    if (strlen(s) != strlen(t)) return 0;
    int mapST[256];  // first string letter -> second string letter
    int mapTS[256];  // second string letter -> first string letter
    memset(mapST, 0, sizeof(mapST));
    memset(mapTS, 0, sizeof(mapTS));
    for (int i = 0; s[i]; i++) {
        unsigned char a = s[i];
        unsigned char b = t[i];
        if (mapST[a] == 0 && mapTS[b] == 0) {
            mapST[a] = b;   // record both directions
            mapTS[b] = a;
        } else if (mapST[a] != b || mapTS[b] != a) {
            return 0;       // conflict in either direction
        }
    }
    return 1;
}

int main(void) {
    printf("%s\n", isIsomorphic("egg", "add") ? "true" : "false");
    printf("%s\n", isIsomorphic("foo", "bar") ? "true" : "false");
    return 0;
}

true
false

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

bool isIsomorphic(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    unordered_map<char, char> mapST;  // s letter -> t letter
    unordered_map<char, char> mapTS;  // t letter -> s letter
    for (int i = 0; i < (int)s.size(); i++) {
        char a = s[i], b = t[i];
        if (mapST.count(a) == 0 && mapTS.count(b) == 0) {
            mapST[a] = b;   // record both directions
            mapTS[b] = a;
        } else if (mapST[a] != b || mapTS[b] != a) {
            return false;   // conflict in either direction
        }
    }
    return true;
}

int main() {
    cout << (isIsomorphic("egg", "add") ? "true" : "false") << endl;
    cout << (isIsomorphic("foo", "bar") ? "true" : "false") << endl;
    return 0;
}

true
false

import java.util.HashMap;
import java.util.Map;

public class Isomorphic {
    static boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Character> mapST = new HashMap<>();  // s -> t
        Map<Character, Character> mapTS = new HashMap<>();  // t -> s
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);
            if (!mapST.containsKey(a) && !mapTS.containsKey(b)) {
                mapST.put(a, b);   // record both directions
                mapTS.put(b, a);
            } else if (mapST.get(a) == null || mapST.get(a) != b
                       || mapTS.get(b) == null || mapTS.get(b) != a) {
                return false;      // conflict in either direction
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isIsomorphic("egg", "add"));
        System.out.println(isIsomorphic("foo", "bar"));
    }
}

true
false

def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    map_st = {}  # s letter -> t letter
    map_ts = {}  # t letter -> s letter
    for a, b in zip(s, t):
        if a in map_st or b in map_ts:
            # both stored partners must match the current pair
            if map_st.get(a) != b or map_ts.get(b) != a:
                return False
        else:
            map_st[a] = b   # record both directions
            map_ts[b] = a
    return True


print(is_isomorphic("egg", "add"))
print(is_isomorphic("foo", "bar"))

True
False

function isIsomorphic(s, t) {
  if (s.length !== t.length) return false;
  const mapST = new Map(); // s letter -> t letter
  const mapTS = new Map(); // t letter -> s letter
  for (let i = 0; i < s.length; i++) {
    const a = s[i], b = t[i];
    if (mapST.has(a) || mapTS.has(b)) {
      // both stored partners must match the current pair
      if (mapST.get(a) !== b || mapTS.get(b) !== a) {
        return false;
      }
    } else {
      mapST.set(a, b); // record both directions
      mapTS.set(b, a);
    }
  }
  return true;
}

console.log(isIsomorphic("egg", "add"));
console.log(isIsomorphic("foo", "bar"));

true
false

Let us read the Python version line by line. The two-map logic is exactly what an interviewer wants explained.

We start with if len(s) != len(t): return False. Different lengths can never be isomorphic, so we stop early.

Then we make two empty dictionaries. map_st remembers what each letter of the first string maps to. map_ts remembers what each letter of the second string maps to.

The loop uses zip(s, t). This pairs up the letters position by position. So a is the letter from the first string and b is the letter from the second string at the same spot.

Inside, the check if a in map_st or b in map_ts asks: have we seen either of these letters before? If yes, the stored partners must match. So map_st.get(a) != b checks that the first letter still points to the same partner. And map_ts.get(b) != a checks the other direction. If either fails, we have a conflict, so we return False.

If neither letter was seen before, we go to the else. We record map_st[a] = b and map_ts[b] = a. So we lock in the mapping both ways.

Why both ways? Take "badc" and "baba". Without the second map you might let two different letters point to the same partner by mistake. The second map catches that. So both maps together guarantee a true one-to-one mapping.

If the loop finishes with no conflict, we return True.

⏱️ Time and Space Complexity

The brute force rebuilds a pattern by scanning back for each letter, so it is O(n²). The two-map method walks the strings once with near-instant lookups, so it is O(n) time. The maps hold at most one entry per distinct letter, so the extra space is bounded by the alphabet size, which is O(1) for a fixed alphabet or O(n) in general terms.

🧩 Key Takeaways

• ✅ Isomorphic means you can swap letters in a steady, one-to-one way to turn one string into the other.
• ✅ One letter must always map to the same partner, and no two letters can share one partner.
• ✅ Use two hash maps, one for each direction, to guard both rules.
• ✅ Walk both strings together and check the stored partners at each position.
• ✅ The two-map method runs in O(n) time, much faster than rebuilding patterns.

🚀 What’s Next?

• Encode and Decode Strings
• Longest Palindromic Substring