VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 02: Hashing

Lesson 2.3 of 12 in this moduleFree

Isomorphic Strings

Can one string's characters be renamed, one-to-one, to produce the other? From trying every renaming, to checking pairs, to two hash maps in one pass, then a canonical first-occurrence code that also groups strings by shape. Then Unicode, streams and pattern-matching at scale.

about 10 min 5 Python examples 2 quick checks

Problem. Strings s and t are isomorphic if the characters of s can be replaced to get t, where:

  • every occurrence of a character is replaced by the same character, and
  • no two different characters map to the same character (a character may map to itself).
text
s = "egg",   t = "add"    →   True    (e → a, g → d)
s = "foo",   t = "bar"    →   False   (o would map to both a and r)
s = "badc",  t = "baba"   →   False   (b and d would both map to b)

ML context. "Same structure, different labels" appears when you compare clusterings (are two cluster assignments the same up to renaming the cluster ids?), align label schemes between datasets, or detect templated strings (log lines, product codes) that share a shape. The trick you learn here, a canonical form, is how you compare things up to renaming.


1. Step 1: Clarify

Question Answer Why it matters
Same length? Guaranteed here; otherwise False Free early exit
Character set? Any ASCII (or Unicode) Decides array versus dict
One-to-one in both directions? Yes The second condition needs a reverse check
Length? Up to 5 × 10⁴ Rules out anything quadratic

2. Step 2: Brute force

Brute force A: check every pair of positions. The two conditions say: for every pair i, j, s[i] == s[j] exactly when t[i] == t[j]. Check them all.

python
def isomorphic_pairs(s, t):
    if len(s) != len(t):
        return False
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            if (s[i] == s[j]) != (t[i] == t[j]):     # equality pattern must match
                return False
    return True


assert isomorphic_pairs("egg", "add")
assert not isomorphic_pairs("foo", "bar")
assert not isomorphic_pairs("badc", "baba")
print("pair check works: O(n²) time, O(1) space")

O(n²): at n = 5 × 10⁴ that's about 1.25 × 10⁹ pair checks. Too slow, so optimise.

(Trying every possible renaming of the alphabet would be far worse: 26! renamings.)


3. Step 3: Optimise

Optimisation 1: build the mapping as you go (two hash maps)

The waste: the pair check rediscovers the same fact ("e goes with a") over and over. Instead, record the mapping the first time you see a character, and check every later occurrence against it.

One map s → t catches "one character with two images" (foo/bar). But it misses "two characters with one image" (badc/baba: b → b and d → b are both fine for the forward map). So keep a second map t → s.

egg and add are isomorphic with e → a and g → d; foo and bar fail because o maps to both a and r; badc and baba fail only in the reverse direction, because b and d both map to b.
Diagram— egg and add are isomorphic with e → a and g → d; foo and bar fail because o maps to both a and r; badc and baba fail only in the reverse direction, because b and d both map to b.
python
import random


def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    s_to_t, t_to_s = {}, {}
    for a, b in zip(s, t):
        if s_to_t.get(a, b) != b or t_to_s.get(b, a) != a:   # conflict in either direction
            return False
        s_to_t[a] = b
        t_to_s[b] = a
    return True


def brute(s, t):
    return len(s) == len(t) and all((s[i] == s[j]) == (t[i] == t[j])
                                    for i in range(len(s)) for j in range(i + 1, len(s)))


for s, t, want in [("egg", "add", True), ("foo", "bar", False), ("badc", "baba", False), ("paper", "title", True), ("", "", True)]:
    assert is_isomorphic(s, t) == want
rng = random.Random(39)
for _ in range(2000):
    n = rng.randint(0, 8)
    s = "".join(rng.choice("abc") for _ in range(n))
    t = "".join(rng.choice("xyz") for _ in range(n))
    assert is_isomorphic(s, t) == brute(s, t)
print("two maps: O(n) time, O(alphabet) space, matches brute force on 2,000 cases")
  • Time: O(n). Space: O(alphabet): at most one entry per distinct character, so O(1) for a fixed alphabet.
  • dict.get(a, b) != b reads as: "if a already has an image, it must be b".

Quick check

Why does 'badc' vs 'baba' pass a single s → t map but fail isomorphism?

  1. The strings have different lengths
  2. The forward map b→b, a→a, d→b, c→a has no conflicts, but b and d both map to b, which breaks one-to-one; only a reverse map t → s catches it
  3. Because d isn't in t
  4. It actually is isomorphic
Show the answer

B. The forward map b→b, a→a, d→b, c→a has no conflicts, but b and d both map to b, which breaks one-to-one; only a reverse map t → s catches it — Injectivity needs checking in the other direction: two source characters must not share an image.

Optimisation 2: compare canonical forms

First principles: isomorphic strings have the same shape: the same pattern of "new character" versus "repeat of the k-th character". Encode each string by replacing every character with the index of its first occurrence. Two strings are isomorphic exactly when their codes are equal.

paper and title both encode to 0 1 0 2 3, so they are isomorphic; foo encodes to 0 1 1 and bar to 0 1 2, so they are not.
Diagram— paper and title both encode to 0 1 0 2 3, so they are isomorphic; foo encodes to 0 1 1 and bar to 0 1 2, so they are not.
python
import random


def shape(s):
    first = {}
    return [first.setdefault(ch, len(first)) for ch in s]     # new char → next id


def is_isomorphic_canonical(s, t):
    return shape(s) == shape(t)


def two_maps(s, t):
    if len(s) != len(t):
        return False
    st, ts = {}, {}
    for a, b in zip(s, t):
        if st.get(a, b) != b or ts.get(b, a) != a:
            return False
        st[a], ts[b] = b, a
    return True


assert shape("paper") == [0, 1, 0, 2, 3] == shape("title")
assert shape("foo") != shape("bar")
rng = random.Random(40)
for _ in range(2000):
    n = rng.randint(0, 8)
    s = "".join(rng.choice("abc") for _ in range(n))
    t = "".join(rng.choice("xyz") for _ in range(rng.choice([n, n + 1])))
    assert is_isomorphic_canonical(s, t) == two_maps(s, t)
print("canonical shape codes agree with the two-map check")

Same O(n) time and O(n) space for the codes. Its real advantage shows up when you compare many strings (next section): a code is hashable, so it can be a dictionary key.


4. When the constraints change

If the constraint becomes… Best approach Time Space
Tiny strings Pair check O(n²) O(1)
Classic Two maps (or two 256-slot arrays for ASCII) O(n) O(alphabet)
Unicode Two dicts O(n) O(distinct chars)
Group m strings by shape Shape code as dict key O(total length) O(total length)
Strings arrive as a stream Two maps, check each pair on arrival O(1) per pair O(alphabet)
Compare two clusterings Same check on the label arrays O(n) O(clusters)

Change A: group many strings by shape

Comparing every pair of m strings with the two-map check is O(m² · n). With a canonical code as a key, it's one pass.

python
from collections import defaultdict


def group_by_shape(words):
    groups = defaultdict(list)
    for w in words:
        first = {}
        key = tuple(first.setdefault(ch, len(first)) for ch in w)
        groups[key].append(w)
    return sorted(sorted(g) for g in groups.values())


assert group_by_shape(["egg", "add", "foo", "bar", "paper", "title", "abc"]) == [
    ["abc", "bar"], ["add", "egg", "foo"], ["paper", "title"]]
print("grouping by shape: one pass over all strings")

Change B: are two clusterings the same up to renaming?

Two runs of k-means give label arrays like [0, 0, 1, 2, 2] and [2, 2, 0, 1, 1]. They describe the same clustering exactly when the label arrays are "isomorphic". Same function, different data.

python
def same_clustering(a, b):
    first_a, first_b = {}, {}
    return [first_a.setdefault(x, len(first_a)) for x in a] == [first_b.setdefault(x, len(first_b)) for x in b]


assert same_clustering([0, 0, 1, 2, 2], [2, 2, 0, 1, 1])
assert not same_clustering([0, 0, 1, 1], [0, 1, 1, 1])
print("two clusterings compared up to renaming the cluster ids")

(When the clusterings are only mostly the same, you'd use a similarity score like the adjusted Rand index; this exact check is its strict special case.)

Quick check

You must group 10⁵ log lines by 'shape' (same pattern of repeated tokens). What's efficient?

  1. Compute each line's first-occurrence code once and use it as a dictionary key: one pass
  2. Run the two-map check on every pair
  3. Sort the lines alphabetically
  4. Compare only lines of equal length pairwise
Show the answer

A. Compute each line's first-occurrence code once and use it as a dictionary key: one pass — A canonical form turns pairwise comparison into hashing.


5. Saying it out loud

"Checking every pair of positions is O(n²). Instead I'll build the mapping as I go with two maps, s to t and t to s, so I catch both a character with two images and two characters sharing one: O(n) time, space bounded by the alphabet. Equivalently, I can encode each string by first-occurrence indices; equal codes mean isomorphic, and the code works as a dict key to group many strings."


Check yourself

  1. What condition on pairs of positions defines isomorphism?
  2. Which failure does the forward map catch, and which needs the reverse map?
  3. Why is the space O(1) for a fixed alphabet?
  4. What is the first-occurrence code of "paper"?
  5. How do you group many strings by shape efficiently?
  6. How does this check apply to comparing two clusterings?
Answers
  1. For all i, j: s[i] == s[j] exactly when t[i] == t[j].
  2. Forward: one character mapped to two images (foo/bar). Reverse: two characters mapped to the same image (badc/baba).
  3. Each map holds at most one entry per distinct character, bounded by the alphabet size.
  4. [0, 1, 0, 2, 3].
  5. Use each string's code (as a tuple) as a dictionary key: one pass.
  6. Two label arrays describe the same clustering exactly when they're isomorphic (equal first-occurrence codes).