Back to solutions

Isomorphic Strings

EasyArrays

Check if characters of s can be consistently mapped to t.

Open problem
Constraints
  • 1 <= |s| <= 5*10^4
  • |s| == |t|

Two-way mapping

Time O(n)Space O(1) (bounded alphabet)

Walk both strings together. Maintain two maps: s-char to t-char and t-char to s-char. At each position, if either map already records a different partner, the mapping is inconsistent. Requiring both directions guarantees the mapping is one-to-one.

Key terms
isomorphism:
A consistent one-to-one renaming that turns one string into the other.
bijection:
A mapping that is one-to-one in both directions (no two keys share a value).
bool isIsomorphic(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    unordered_map<char, char> st, ts;
    for (size_t i = 0; i < s.size(); i++) {
        char a = s[i], b = t[i];
        if (st.count(a) && st[a] != b) return false;
        if (ts.count(b) && ts[b] != a) return false;
        st[a] = b; ts[b] = a;
    }
    return true;
}
Step by step
  1. If lengths differ, return false immediately.
  2. For each index, let a = s[i], b = t[i].
  3. If a already maps to something other than b, fail; if b already maps to something other than a, fail.
  4. Record a->b and b->a, then continue. If the loop finishes, return true.