Isomorphic String Mapping — Problem Statement & Solution Guide
Problem Description
Given two strings s and t, decide whether a bijective (one‑to‑one and onto) correspondence can be established between the characters of s and those of t. In other words, each distinct character in s must map to a unique character in t, and each distinct character in t must be mapped from exactly one character in s. Return true if such a mapping exists; otherwise return false. The strings may contain any printable ASCII symbols and are provided in the order s followed by t.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Isomorphic String Mapping"
WHY DOES IT MATTER?
Detecting a one‑to‑one correspondence between two sequences is a foundational pattern for many equivalence problems, such as checking graph isomorphism, validating serialization formats, or ensuring consistent key‑value contracts in APIs.
OPTIMIZATION CHALLENGE
The insight is that you can enforce both forward and reverse constraints simultaneously with two constant‑time hash tables while iterating once, collapsing what would be a quadratic verification into linear time.
REAL-WORLD CONNECTION
Think of a URL shortener service: each long URL must map to a unique short code and vice‑versa; maintaining two lookup tables guarantees that no two long URLs share the same short code, mirroring the bijective check in this problem.
During the interview, initialize both maps before the loop, update them only when you encounter a new pair, and immediately return false on any inconsistency – this avoids extra conditionals later and keeps the code clean.
COMPLEXITY AT A GLANCE
O(n)O(σ)Core Theory — Why This Approach?
The problem reduces to checking whether a bijection exists between the character sets of two strings. A bijective mapping requires two constraints: each character in s maps to exactly one character in t (functionality) and no two distinct characters in s map to the same character in t (injectivity). A naive double‑loop that compares every character pair leads to O(n^2) time and quickly exceeds limits for long inputs. The optimal paradigm leverages two hash tables (or fixed‑size arrays for ASCII/Unicode) to record the forward and reverse mappings while scanning the strings once. As each position i is processed, we verify that the current characters either establish a new consistent pair or respect an existing pair, guaranteeing O(n) time and O(σ) space, where σ is the size of the character set.
The forward map (s→t) ensures that a character in s never points to two different characters in t, while the reverse map (t→s) guarantees the injective property. If either map contradicts the current pair, the bijection fails. This two‑map technique is a classic example of using constant‑time look‑ups to enforce one‑to‑one relationships, a pattern that appears in many string‑isomorphism and pattern‑matching problems.
Interview Questions on This Problem
Q1How would you modify the solution if the strings could contain Unicode characters beyond the ASCII range?
Use language‑native hash maps (e.g., unordered_map<char32_t,int> in C++ or dict in Python) instead of fixed‑size arrays, because the alphabet size is no longer bounded; the algorithmic steps remain identical.
Q2Can you solve the isomorphic string problem using a single hash map instead of two? Explain the trade‑off.
Yes, you can store a combined key like "sChar#tChar" in a set and also ensure that the number of unique s characters equals the number of unique t characters, but this loses the immediate injectivity check and may require an extra pass or additional data structures, making the code less clear and slightly increasing constant factors.
Q3Why does checking length equality before any mapping checks matter in an interview setting?
If the strings differ in length, a bijection is impossible, so an early length check eliminates unnecessary work and demonstrates to the interviewer that you consider trivial edge cases upfront.
Examples
Input
s = "paper", t = "title"
Output
true
Explanation: Map p→t, a→i, e→l, r→e. All mappings are unique and consistent, and the reverse mapping t→p, i→a, l→e, e→r also holds, so the strings are isomorphic.
Input
s = "abca", t = "zbxz"
Output
true
Explanation: Create mappings a→z, b→b, c→x. The fourth character a again maps to z, which matches the earlier mapping. The reverse mapping z→a, b→b, x→c is also one‑to‑one, therefore the strings are isomorphic.
Input
s = "foo", t = "bar"
Output
false
Explanation: The first character f would map to b. The next two characters o would both need to map to a and r simultaneously, which is impossible, breaking the bijection. Hence the strings are not isomorphic.
Constraints
- 1 <= s.length == t.length <= 10^5
- s and t consist of printable ASCII characters (code 32 to 126)
- The algorithm should run in O(n) time and O(1) additional space apart from the hash tables used for mapping
Optimal Approach & Strategy
Maintain two hash tables for forward and reverse mappings while scanning once, validating each pair in constant time.
Brute Force Approach
Compare every character of s with every character of t to build all possible mappings, leading to exponential or quadratic time.
Verified Code Solutions
function isIsomorphic(s, t) {
if (s.length !== t.length) return false;
const mapST = new Map();
const mapTS = new Map();
for (let i = 0; i < s.length; i++) {
const a = s[i];
const b = t[i];
if (mapST.has(a) && mapST.get(a) !== b) return false;
if (mapTS.has(b) && mapTS.get(b) !== a) return false;
mapST.set(a, b);
mapTS.set(b, a);
}
return true;
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
if (input.length >= 2) {
const s = input[0];
const t = input[1];
console.log(isIsomorphic(s, t) ? "true" : "false");
}#include <bits/stdc++.h>
using namespace std;
bool isIsomorphic(const string& s, const string& t) {
if (s.size() != t.size()) return false;
unordered_map<char,char> mapST, mapTS;
for (size_t i=0;i<s.size();++i) {
char a=s[i], b=t[i];
if (mapST.count(a) && mapST[a]!=b) return false;
if (mapTS.count(b) && mapTS[b]!=a) return false;
mapST[a]=b;
mapTS[b]=a;
}
return true;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);string s,t;while(cin>>s>>t){cout<<(isIsomorphic(s,t)?"true":"false")<<"\n";}return 0;}import java.util.*;
public class Main {
public static boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Character> mapST = new HashMap<>();
Map<Character, Character> mapTS = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i);
char b = t.charAt(i);
if (mapST.containsKey(a) && mapST.get(a) != b) return false;
if (mapTS.containsKey(b) && mapTS.get(b) != a) return false;
mapST.put(a, b);
mapTS.put(b, a);
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (sc.hasNext()) {
String s = sc.next();
if (sc.hasNext()) {
String t = sc.next();
System.out.println(isIsomorphic(s, t));
}
}
sc.close();
}
}def is_isomorphic(s: str, t: str) -> bool:
if len(s) != len(t):
return False
map_st, map_ts = {}, {}
for a, b in zip(s, t):
if a in map_st and map_st[a] != b:
return False
if b in map_ts and map_ts[b] != a:
return False
map_st[a] = b
map_ts[b] = a
return True
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if len(data) >= 2:
s, t = data[0], data[1]
print(str(is_isomorphic(s, t)).lower())function isIsomorphic(s, t) {
if (s.length !== t.length) return false;
const mapST = new Map();
const mapTS = new Map();
for (let i = 0; i < s.length; i++) {
const a = s[i];
const b = t[i];
if (mapST.has(a) && mapST.get(a) !== b) return false;
if (mapTS.has(b) && mapTS.get(b) !== a) return false;
mapST.set(a, b);
mapTS.set(b, a);
}
return true;
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
if (input.length >= 2) {
const s = input[0];
const t = input[1];
console.log(isIsomorphic(s, t) ? "true" : "false");
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.