☕ DSA Java Articles

Topics › Strings › Basic and Easy String Problems

Isomorphic String

Easy TUF ID 393 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Two strings s and t are isomorphic if the characters of s can be replaced to obtain t, subject to two rules: every occurrence of a character must be replaced by the same character (the replacement is a function), and no two different characters may be replaced by the same character (the function is one-to-one). A character may map to itself. Return true if s and t are isomorphic and false otherwise.

Put differently, s and t have the same “shape”: wherever s repeats a character, t repeats a character at exactly the same positions, and vice versa.

Constraints: 0 ≤ |s|, |t| ≤ 5 × 10^4; the strings consist of printable ASCII characters. Strings of different lengths are never isomorphic.

Example 1

s = "egg", t = "add"
answer = true          // e -> a, g -> d

Example 2

s = "foo", t = "bar"
answer = false         // o would have to become both a and r

Example 3

s = "badc", t = "baba"
answer = false         // b -> b and then d -> b: two characters with the same image

Approach 1: Brute force, compare every pair of positions

Intuition. Forget about building the mapping and look at what it implies. If positions i and j hold the same character in s, the function sends both to the same character, so t[i] == t[j]. Conversely, if t[i] == t[j] then, because the function is one-to-one, s[i] == s[j]. So isomorphism is equivalent to: for every pair of positions, “equal in s” and “equal in t” are either both true or both false. This is a complete characterisation, and checking it needs no data structure at all.

Why is the condition sufficient? If it holds, define f(s[i]) = t[i]. It is well defined (equal s characters get equal t characters) and injective (different s characters get different t characters), which is exactly what the problem demands.

Algorithm.

  1. If the lengths differ, return false.
  2. For every pair i < j: compute sameInS = s[i] == s[j] and sameInT = t[i] == t[j].
  3. If sameInS != sameInT, return false.
  4. If every pair agrees, return true.
static boolean bruteForce(String s, String t) {
    if (s.length() != t.length()) return false;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            boolean sameInS = s.charAt(i) == s.charAt(j);
            boolean sameInT = t.charAt(i) == t.charAt(j);
            if (sameInS != sameInT) return false;
        }
    }
    return true;
}

Complexity. Time O(n^2): n(n-1)/2 pairs, constant work each. Space O(1).

At n = 5 × 10^4 that is about 1.25 × 10^9 comparisons, too slow. But the pairwise view explains why the linear solutions below are correct: each of them is a way to check all pairs implicitly.

Approach 2: Better, two hash maps

Intuition. Build the mapping as you go. A map forward records what each character of s has been sent to. When we meet a = s[i] paired with b = t[i], there are two cases. If a has been seen, its recorded image must be b, otherwise the function would be ill defined. If a is new, we would like to record a -> b, but first we must make sure b is not already the image of some other character: that is what the second map backward (from t characters to s characters) is for. Without it "ab" and "aa" would be accepted, because a -> a and b -> a are each individually consistent.

Algorithm.

  1. If the lengths differ, return false.
  2. For each index i, let a = s[i], b = t[i].
    • If forward has no entry for a: if backward already contains b, return false; otherwise record a -> b in forward and b -> a in backward.
    • If forward maps a to something other than b, return false.
  3. Return true.
static boolean better(String s, String t) {
    if (s.length() != t.length()) return false;
    Map<Character, Character> forward = new HashMap<>();
    Map<Character, Character> backward = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i), b = t.charAt(i);
        Character mappedA = forward.get(a);
        if (mappedA == null) {
            if (backward.containsKey(b)) return false;   // b is already the image of another character
            forward.put(a, b);
            backward.put(b, a);
        } else if (mappedA != b) {
            return false;                                  // a was mapped to a different character earlier
        }
    }
    return true;
}

Complexity. Time O(n): one pass with constant-time map operations on average. Space O(k) where k is the number of distinct characters, at most 128 for ASCII, so effectively constant.

A common shortcut is to keep only one of the two checks: either the backward.containsKey(b) test for a new a, or the mappedA != b consistency test. Both are needed. The first rejects "ab"/"aa" (two sources, one image) and the second rejects "foo"/"bar" (one source, two images).

Note the comparison mappedA != b: mappedA is a Character and b is a char, so Java unboxes mappedA and compares the primitive values. Comparing two Character objects with != would compare references and is a classic bug; comparing a Character with a char is safe.

Approach 3: Optimal, compare the last-seen positions

Intuition. The two maps store characters, but all we ever ask is “have these two characters been paired with each other before, and only with each other?” There is a neater invariant. Record, for each character, the index at which it was last seen, separately for s and t. At position i, a = s[i] and b = t[i] are consistent exactly when lastS[a] == lastT[b]:

So “the last positions agree at every step” is equivalent to the pairwise condition from Approach 1, but it is checked in O(1) per step. Storing i + 1 instead of i lets 0 mean “never seen” without a separate boolean array.

Algorithm.

  1. If the lengths differ, return false.
  2. Create lastS[256] and lastT[256], all zero.
  3. For each i: if lastS[s[i]] != lastT[t[i]], return false; otherwise set both to i + 1.
  4. Return true.
static boolean optimal(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] lastS = new int[256], lastT = new int[256];     // last position + 1; 0 means not seen yet
    for (int i = 0; i < s.length(); i++) {
        int a = s.charAt(i), b = t.charAt(i);
        if (lastS[a] != lastT[b]) return false;
        lastS[a] = i + 1;
        lastT[b] = i + 1;
    }
    return true;
}

Dry run on s = "badc", t = "baba":

i a = s[i] b = t[i] lastS[a] lastT[b] result
0 b b 0 0 agree, set both to 1
1 a a 0 0 agree, set both to 2
2 d b 0 1 differ, return false

And on s = "paper", t = "title":

i a b lastS[a] lastT[b] result
0 p t 0 0 set both to 1
1 a i 0 0 set both to 2
2 p t 1 1 agree, set both to 3
3 e l 0 0 set both to 4
4 r e 0 0 set both to 5; loop ends, return true

Complexity. Time O(n). Space O(1): two arrays of 256 integers regardless of the input size.

Why 256 rather than 128? The problem promises printable ASCII, so 128 would do; 256 covers every char value that fits in a byte and costs nothing. For arbitrary Unicode input the arrays would have to grow to 65 536 entries or be replaced by the hash maps of Approach 2.

Edge cases and pitfalls