Isomorphic Strings: Character Mapping with Hash Maps

LeetCode 205, Isomorphic Strings, asks you to determine whether two strings have a one-to-one character mapping. If you can replace every character in s with another character (consistently) to get t, and no two characters map to the same target, the strings are isomorphic. If you have already solved Valid Anagram and Ransom Note, this is a natural next step into hash map territory, but the twist here is that the mapping must work in both directions.

Why this problem matters

Isomorphic Strings looks simple on the surface, but it introduces a concept you will see again and again: bidirectional mapping. In Valid Anagram, you just compare character counts. Here, you need to verify that a structural relationship holds. The characters themselves do not matter, only the pattern of repetition.

This distinction matters because many real problems come down to pattern equivalence. Checking whether two strings follow the same structure shows up in word pattern problems, encoding schemes, and even compiler design. The two-hash-map technique you learn here is the core tool for all of those.

The other reason this problem matters is that it teaches you to think about constraints carefully. A one-directional mapping is not enough. If you only check that each character in s maps to one character in t, you miss cases where two characters in s map to the same character in t. You need the reverse check too.

Thinking it through

Given s = "egg" and t = "add", you want to verify:

1. Every character in s always maps to the same character in t. The first 'g' maps to 'd', and the second 'g' also maps to 'd'. Good.
2. Every character in t always maps back to the same character in s. The first 'd' comes from 'g', and the second 'd' also comes from 'g'. Good.

Now consider s = "foo" and t = "bar". The character 'o' would need to map to both 'a' and 'r'. That is a conflict. Not isomorphic.

And consider s = "badc" and t = "baba". Here 'd' maps to 'b' and 'c' maps to 'a', but 'b' in s already maps to 'b' in t. Meanwhile 'b' in t would need to map back to both 'b' and 'd' in s. The reverse direction has a conflict. This is why you need two maps.

The brute force approach

The most direct approach is to check if the transformation pattern is the same for both strings. You can convert each string to a canonical "pattern" by mapping first occurrences to indices:

def isIsomorphic(s, t):
    def pattern(word):
        mapping = {}
        result = []
        for ch in word:
            if ch not in mapping:
                mapping[ch] = len(mapping)
            result.append(mapping[ch])
        return result

    return pattern(s) == pattern(t)

This works. "egg" becomes [0, 1, 1] and "add" becomes [0, 1, 1]. They match. "foo" becomes [0, 1, 1] and "bar" becomes [0, 1, 2]. They do not match.

The time complexity is O(n) and the space is O(n) for the result lists. It is correct, but it creates intermediate data structures that you do not strictly need. The two-hash-map approach is more direct and avoids building those lists.

Two hash maps: the clean solution

The idea is simple: maintain two dictionaries. One maps characters from s to t, and the other maps characters from t back to s. At each position, check that neither mapping has a conflict. If both maps agree (or the character is new), the mapping is consistent.

def isIsomorphic(s, t):
    s_to_t = {}
    t_to_s = {}

    for cs, ct in zip(s, t):
        if cs in s_to_t and s_to_t[cs] != ct:
            return False
        if ct in t_to_s and t_to_s[ct] != cs:
            return False
        s_to_t[cs] = ct
        t_to_s[ct] = cs

    return True

Walk through each pair of characters in lockstep. For every position:

• Check forward mapping. If cs already has a mapping in s_to_t, verify it points to ct. If it points somewhere else, return False.
• Check reverse mapping. If ct already has a mapping in t_to_s, verify it points to cs. If it points somewhere else, return False.
• Record the mapping. If both checks pass, store cs -> ct and ct -> cs.

If you make it through the entire string without a conflict, the strings are isomorphic.

Why you need two maps

A common mistake is to only use one map (s_to_t) and skip the reverse. Consider s = "ab" and t = "aa":

• Position 0: 'a' maps to 'a'. Record it.
• Position 1: 'b' maps to 'a'. Record it.

With only one map, this looks fine. Both lookups succeed. But the mapping is broken because two different characters in s ('a' and 'b') both map to the same character in t ('a'). The reverse map catches this: when you try to map 'a' in t back to 'b' in s, it conflicts with the existing mapping 'a' -> 'a'.

Bidirectional checking ensures the mapping is truly one-to-one. Without it, you get false positives.

Complexity analysis

*O(1) because the character set is bounded (at most 128 ASCII characters or 26 lowercase letters, depending on the problem constraints). Each map holds at most one entry per unique character. In practice, the maps never grow beyond the size of the character set, which is constant.

Both approaches are O(n) in time. The two-hash-map approach is more space-efficient because it does not create intermediate lists. It is also the approach interviewers expect, because it demonstrates that you understand bidirectional constraints.

Edge cases to watch for

• Different lengths. If len(s) != len(t), they cannot be isomorphic. The problem guarantees equal lengths, but adding an early check is a good habit.
• Empty strings. Two empty strings are isomorphic. The loop body never executes, and we return True.
• Single characters. s = "a", t = "b" returns True. Any single character can map to any other single character.
• All same characters. s = "aaa", t = "bbb" returns True. s = "aaa", t = "bba" returns False because 'a' would need to map to both 'b' and 'a'.
• Self-mapping. s = "abc", t = "abc" returns True. A character can map to itself.

The building blocks

This problem is built from one core technique: bidirectional hash map mapping. Where frequency counting asks "how many?", this pattern asks "which one?" It is a structural comparison rather than a quantitative one.

The template looks like this:

forward = {}
backward = {}
for a, b in zip(seq1, seq2):
    if a in forward and forward[a] != b:
        return False
    if b in backward and backward[b] != a:
        return False
    forward[a] = b
    backward[b] = a
return True

You will see this exact pattern in:

• Word Pattern (LeetCode 290): same idea, but mapping words to characters instead of characters to characters
• Isomorphic Strings (this problem): the pure character-to-character version
• Any encoding validation: checking that a substitution cipher is consistent

The key insight is that a one-to-one mapping requires verification in both directions. Whenever a problem says "consistent mapping" or "one-to-one correspondence," reach for two hash maps.

From understanding to recall

Isomorphic Strings is an easy-rated problem, and the solution is short. But the two-hash-map pattern is the important takeaway. Three weeks from now, when you encounter Word Pattern or a custom encoding problem, you want the bidirectional check to be automatic. You should not need to re-derive why one map is not enough.

Spaced repetition locks this in. You practice writing the two-map solution from scratch at increasing intervals. After a few cycles, the pattern is in your fingers. When a problem says "consistent mapping," you already know the approach before you finish reading.

Related posts

• Valid Anagram - The frequency counting cousin of this problem, checking whether two strings have the same character counts rather than a structural mapping
• Ransom Note - Another hash map problem that checks a subset relationship between character frequencies
• Group Anagrams - Uses hash maps to group strings by their character signature, a different angle on string-to-string comparison