The O(n) Club: Isomorphic Strings — The Interview Trap That Snags Smart Devs

The O(n) Club: Isomorphic Strings — The Interview Trap That Snags Smart Devs

⚡ TL;DR

Want to see if two strings can become each other by swapping letters, and only swapping uniquely? The lazy way is to brute-force mappings; the smart way is to track last-seen positions for each character in both strings at once. If the histories line up, you’re golden. Here’s Java’s greatest hits condensed:

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] sMap = new int[256], tMap = new int[256];
    for (int i = 0; i < s.length(); i++) {
        char c1 = s.charAt(i), c2 = t.charAt(i);
        if (sMap[c1] != tMap[c2]) return false;
        sMap[c1] = tMap[c2] = i + 1;
    }
    return true;
}

🧠 How Devs Usually Mess This Up

Most devs lunge for a one-way mapping from s to t and call it a day—congrats, you’ve just failed on ab and aa. Even worse, some let multiple letters map to the same destination. Like two chefs trying to share the same apron at once—very awkward, stains everywhere, and no one’s happy. Go both ways or go home!

🔍 What’s Actually Going On

Pretend each letter in s gets a costume change to become t, but each costume is custom-tailored for one character only. No off-the-rack, no hand-me-downs. For every swap, you better be able to swap back uniquely, or someone’s code identity gets stolen. That’s why we need to check in both directions, like two mutexes making eye contact awkwardly in a codebase.

🛠️ PseudoCode

• Step 1: If lengths don’t match, don’t even bother—return false.
• Step 2: Set up two trackers (think: attendance sheets) for last positions seen.
  

  int[] sMap = new int[256];
  int[] tMap = new int[256];

• Step 3: Loop through each character. At every spot, check if the histories from s and t align.
  

  for (int i = 0; i < s.length(); i++) {
    if (sMap[s.charAt(i)] != tMap[t.charAt(i)]) return false;
    sMap[s.charAt(i)] = tMap[t.charAt(i)] = i + 1;
  }

• Step 4: If you finish the loop without finding a mismatch, victory is yours!

  return true;

💻 The Code

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] sMap = new int[256];
    int[] tMap = new int[256];
    for (int i = 0; i < s.length(); i++) {
        char c1 = s.charAt(i);
        char c2 = t.charAt(i);
        if (sMap[c1] != tMap[c2]) return false;
        sMap[c1] = tMap[c2] = i + 1;
    }
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Different lengths? Not isomorphic. Next!
• One-way mapping? Isomorphic requires a unique partnership—check both directions, or your code will fail the loyalty test.
• Non-ASCII? Use a HashMap if Unicode sneaks in (emojis love to crash these parties).
• Time? O(n), straight-up. Space? Just two arrays (constant if limited charset). No drama unless you blow out the alphabet.

🧠 Interviewer Brain-Tattoo

“Checking only one mapping in an isomorphic string interview is like wearing only one sock to a client meeting: bold, memorable, and a guaranteed fail.”