Isomorphic Strings — Problem Statement & Solution Guide
Problem Description
Two strings, s and t, are considered isomorphic if there exists a one-to-one mapping between the characters of s and the characters of t. This means that every character in s maps to exactly one character in t, and every character in t maps to exactly one character in s. No two distinct characters in s can map to the same character in t, and vice versa. Note that a character may map to itself.
Given two strings s and t, determine whether they are isomorphic. Return true if they are, and false otherwise.
The mapping must be consistent throughout the entire length of the strings. For example, if 'a' maps to 'x' at one position, it must map to 'x' at every other position where 'a' appears in s. Similarly, if 'x' in t is mapped from 'a' in s, no other character in s can map to 'x'.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Isomorphic Strings"
WHY DOES IT MATTER?
This pattern is essential for understanding bijections and state management in linear scans. It teaches candidates how to enforce bidirectional constraints using hash maps, a skill directly applicable to problems involving graph isomorphism, encoding/decoding, and data consistency checks.
OPTIMIZATION CHALLENGE
The key insight is recognizing that a single hash map is not enough to enforce the one-to-one constraint. You must either maintain two maps (one for s->t and one for t->s) or use a single map that stores the last seen character in t for each character in s, and verify that the current character in t matches the stored one. This reduces the space complexity to O(k) where k is the size of the alphabet, which is constant for ASCII.
REAL-WORLD CONNECTION
This is analogous to database foreign key constraints. Just as a foreign key must reference a unique primary key, the mapping from s to t must be unique in both directions. It is also similar to URL rewriting rules where each path segment must map to a unique handler, ensuring no two distinct paths resolve to the same endpoint.
In an interview, do not just code the solution. Explicitly state the 'two-way' constraint. Many candidates fail by only checking s->t. Mentioning that you need to ensure t->s is also a function demonstrates a deep understanding of the problem's mathematical properties.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem of determining if two strings are isomorphic fundamentally revolves around the concept of a bijective mapping, or a one-to-one correspondence between two sets. A naive approach might attempt to check every possible permutation of characters, which is computationally infeasible for large inputs due to factorial complexity. Instead, the optimal paradigm utilizes hashing to maintain state during a linear scan. By tracking the mapping from characters in string s to characters in string t, we can verify consistency in O(n) time. However, a critical theoretical nuance is that a simple map from s to t is insufficient because it does not enforce the 'one-to-one' constraint in the reverse direction. For example, if s is 'ab' and t is 'aa', the map a->a and b->a is valid for s to t, but invalid for t to s because two distinct characters in s map to the same character in t. Therefore, the theory requires maintaining two separate hash maps or a single map that tracks the last seen character to ensure mutual exclusivity.
Interview Questions on This Problem
Q1At a fintech platform, we need to verify if two encrypted transaction logs are structurally identical without decrypting them. How would you adapt the isomorphic string logic to handle large log files that do not fit in memory?
I would use an external sorting or streaming approach. Since the strings are too large for memory, I would process them in chunks. However, isomorphism is a global property. A better approach for large data is to compute a cryptographic hash of the structural pattern. For each string, I would generate a normalized 'pattern key' where the first unique character is mapped to '1', the second to '2', etc. If the pattern keys of both logs are identical, they are isomorphic. This reduces the problem to comparing two fixed-size hashes or pattern strings, which is O(n) time and O(1) space (if we only store the current pattern state) or O(k) where k is the alphabet size.
Q2In a high-growth startup, we are building a feature to detect duplicate user content based on structural similarity. If we extend 'isomorphic' to 'k-isomorphic' (where characters can be swapped if they are within distance k), how does the complexity change?
Standard isomorphism is O(n). For k-isomorphism, the problem becomes significantly harder, potentially NP-hard depending on the definition of 'distance'. However, if 'distance' refers to character frequency or position constraints, we might need to use dynamic programming or sliding window techniques. For a standard interview, I would clarify the definition of 'k'. If it means allowing up to k mismatches, it becomes a string matching problem with k errors, solvable in O(n*k) using DP. If it means structural similarity with limited edits, it relates to edit distance. The key is to define the constraint precisely before coding.
Q3At a global product company, our API returns JSON objects. How can we use isomorphic string principles to quickly check if two JSON structures are equivalent in shape, ignoring the actual values?
I would serialize the JSON structure into a canonical string representation that captures only the keys and nesting depth, ignoring values. For example, {"a": 1, "b": {"c": 2}} becomes "a,b,c" with depth markers. Then, I would check if the two canonical strings are isomorphic. This allows us to verify structural equivalence in O(n) time, where n is the size of the JSON, without parsing the full objects into memory. This is crucial for caching and validation layers where performance is critical.
Examples
Input
s = "egg", t = "add"
Output
true
Explanation: Step 1: Map 'e' to 'a'. Step 2: Map 'g' to 'd'. Step 3: Map 'g' to 'd' (consistent). All mappings are one-to-one. Return true.
Input
s = "foo", t = "bar"
Output
false
Explanation: Step 1: Map 'f' to 'b'. Step 2: Map 'o' to 'a'. Step 3: Attempt to map 'o' to 'r'. Conflict: 'o' already maps to 'a'. Return false.
Input
s = "paper", t = "title"
Output
true
Explanation: Step 1: Map 'p' to 't'. Step 2: Map 'a' to 'i'. Step 3: Map 'p' to 't' (consistent). Step 4: Map 'e' to 'l'. Step 5: Map 'r' to 'e'. All mappings are one-to-one. Return true.
Input
s = "ab", t = "aa"
Output
false
Explanation: Step 1: Map 'a' to 'a'. Step 2: Attempt to map 'b' to 'a'. Conflict: 'a' in t is already mapped from 'a' in s. Return false.
Constraints
- 1 <= s.length <= 5 * 10^4
- t.length == s.length
- s and t consist of lowercase English letters.
Optimal Approach & Strategy
Use two hash maps to maintain a one-to-one mapping between characters of s and t. Iterate through both strings simultaneously, updating and checking the maps to ensure consistency and uniqueness in both directions. This achieves O(n) time complexity and O(k) space complexity, where k is the size of the character set.
Brute Force Approach
Generate all possible permutations of the characters in string t and check if any permutation matches the structure of string s. This approach has a time complexity of O(n * n!), which is infeasible for any string longer than 10-12 characters.
Verified Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
const s = input[0]||"";
const t = input[1]||"";
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], 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;
}
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> m1,m2;
for(size_t i=0;i<s.size();++i){
char a=s[i], b=t[i];
if(m1.count(a)&&m1[a]!=b) return false;
if(m2.count(b)&&m2[b]!=a) return false;
m1[a]=b; m2[b]=a;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s,t; if(!(cin>>s>>t)) return 0;
cout<<(isIsomorphic(s,t)?"true":"false");
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()) return;
String s = sc.next();
if (!sc.hasNext()) return;
String t = sc.next();
System.out.print(isIsomorphic(s, t) ? "true" : "false");
}
}import sys
def isIsomorphic(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
def main():
data = sys.stdin.read().strip().split()
if len(data) < 2:
return
s, t = data[0], data[1]
print('true' if isIsomorphic(s, t) else 'false')
if __name__ == '__main__':
main()const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
const s = input[0]||"";
const t = input[1]||"";
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], 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;
}
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.