Isomorphic Strings

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace

Problem Statement❯

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. The replacement must be consistent — every character in s must map to exactly one character in t, and no two characters from s can map to the same character in t.

The character mapping should be one-to-one and should preserve the order of characters. Return true if the strings are isomorphic, otherwise return false.

Examples❯

s t Output Description
"egg" "add" true 'e' → 'a', 'g' → 'd' — consistent mapping
"foo" "bar" false 'o' maps to two different characters, which breaks the rule
"paper" "title" true 'p' → 't', 'a' → 'i', 'e' → 'l', 'r' → 'e'
"ab" "aa" false 'a' → 'a' and 'b' → 'a' — two characters from 's' map to same char in 't'
"abc" "def" true Each character maps uniquely and consistently
"" "" true Both strings are empty — trivially isomorphic
"" "abc" false One string is empty, the other is not
"abc" "" false One string is empty, the other is not
"abca" "zbxz" true 'a' → 'z', 'b' → 'b', 'c' → 'x' — all mappings valid
"abca" "zbxy" false 'a' maps to both 'z' and 'y' — mapping is inconsistent

Visualization Player

Solution❯

To check whether two strings are isomorphic, we need to understand whether we can map each character in the first string to a unique character in the second string — and do so consistently throughout the entire string.

Imagine we are translating every character from s to t. If 'a' in s maps to 'x' in t, then every time we see 'a' in s, it must be translated to 'x'. If we see 'a' later mapping to a different character (like 'y'), the strings are not isomorphic.

We also need to make sure that no two different characters in s map to the same character in t. For example, if both 'a' and 'b' map to 'x', that breaks the one-to-one requirement.

To implement this, we can use two hash maps (or dictionaries):

  • s_to_t: Maps characters from s to t.
  • t_to_s: Maps characters from t to s.

As we iterate through the characters of both strings, we:

  • Check if the current character from s has already been mapped to something in t. If it has, and the mapping doesn't match the current character in t, we return false.
  • Similarly, we check that the character in t hasn't already been assigned to a different character from s.

If we finish the loop and all mappings are valid, we return true.

Special Cases to Consider:

  • Empty strings: Two empty strings are trivially isomorphic — no characters means no conflicts.
  • Different lengths: If the strings are of unequal length, they can never be isomorphic, because we can't map characters one-to-one.
  • Repeated characters: It's okay if a character appears multiple times — as long as it always maps to the same character in the other string, and no conflicts arise.

This explanation focuses on helping beginners reason through character mapping with clarity before worrying about code or efficiency.

Algorithm Steps❯

  1. Initialize two HashMaps: s_to_t and t_to_s.
  2. Loop through each character in both strings.
  3. For each character pair (sc, tc) from s and t:
    • If sc is mapped in s_to_t, it must map to tc.
    • If tc is mapped in t_to_s, it must map to sc.
  4. If any mismatch is found, return false.
  5. After the loop, return true.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
def is_isomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    s_to_t = {}
    t_to_s = {}

    for sc, tc in zip(s, t):
        if sc in s_to_t:
            if s_to_t[sc] != tc:
                return False
        else:
            s_to_t[sc] = tc

        if tc in t_to_s:
            if t_to_s[tc] != sc:
                return False
        else:
            t_to_s[tc] = sc

    return True

# Example Usage
print(is_isomorphic("egg", "add"))  # True
print(is_isomorphic("foo", "bar"))  # False

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)We traverse both strings once, checking and updating maps in constant time.
Average CaseO(n)Each character mapping takes constant time; total work is proportional to string length.
Worst CaseO(n)In the worst case, every character in both strings is unique and requires a mapping.

Space Complexity

O(n)

Explanation: Two hash maps are used that at most store all unique characters of the strings.