Isomorphic Strings
EasyPrompt
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
Example 1:
Input: s = "egg", t = "add"
Output: true
Explanation:
The strings s and t can be made identical by:
- Mapping
'e'to'a'. - Mapping
'g'to'd'.
Example 2:
Input: s = "foo", t = "bar"
Output: false
Explanation:
The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.
Example 3:
Input: s = "paper", t = "title"
Output: true
Constraints:
1 <= s.length <= 5 * 104t.length == s.lengthsandtconsist of any valid ascii character.
Approaches
3 approaches with complexity analysis and trade-offs.
Use two character arrays to store the mappings between characters of both strings. Iterate through both strings simultaneously and check if the mappings are consistent.
Algorithm
- Create two character arrays sToT and tToS of size 256
- Iterate through both strings simultaneously
- For each character pair:
- Check if sChar has a mapping in sToT
- If no mapping exists, create one
- If mapping exists, verify it matches tChar
- Repeat the same process for tChar in tToS
- Return true if all mappings are consistent
Walkthrough
This approach uses two character arrays of size 256 (for ASCII characters) to store the mappings from s to t and t to s. For each character in both strings, we check if there's already a mapping. If there is, we verify it matches the current characters. If there isn't, we create new mappings in both directions.
public boolean isIsomorphic(String s, String t) { char[] sToT = new char[256]; char[] tToS = new char[256]; for (int i = 0; i < s.length(); i++) { char sChar = s.charAt(i); char tChar = t.charAt(i); // Check mapping from s to t if (sToT[sChar] == 0) { sToT[sChar] = tChar; } else if (sToT[sChar] != tChar) { return false; } // Check mapping from t to s if (tToS[tChar] == 0) { tToS[tChar] = sChar; } else if (tToS[tChar] != sChar) { return false; } } return true;}Complexity
Time
O(n) where n is the length of the strings
Space
O(1) since we use fixed-size arrays of 256 characters
Trade-offs
Pros
Simple implementation
Easy to understand
Works with ASCII characters
Cons
Uses more space than necessary if strings only contain a small subset of ASCII characters
Not suitable for Unicode strings without modification
Use two HashMaps to store the character mappings between the strings. This approach is more flexible and can handle any character set.
Algorithm
- Create two HashMaps for storing mappings from s to t and t to s
- Iterate through both strings simultaneously
- For each character pair:
- Check if sChar has a mapping in sMap
- If no mapping exists, create one
- If mapping exists, verify it matches tChar
- Repeat the same process for tChar in tMap
- Return true if all mappings are consistent
Walkthrough
This approach uses two HashMaps to maintain the bidirectional mapping between characters of both strings. We iterate through both strings simultaneously and store the mappings in both directions. If we find any inconsistency in the mappings, we return false.
public boolean isIsomorphic(String s, String t) { Map<Character, Character> sMap = new HashMap<>(); Map<Character, Character> tMap = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char sChar = s.charAt(i); char tChar = t.charAt(i); // Check mapping from s to t if (!sMap.containsKey(sChar)) { sMap.put(sChar, tChar); } else if (sMap.get(sChar) != tChar) { return false; } // Check mapping from t to s if (!tMap.containsKey(tChar)) { tMap.put(tChar, sChar); } else if (tMap.get(tChar) != sChar) { return false; } } return true;}Complexity
Time
O(n) where n is the length of the strings
Space
O(k) where k is the number of unique characters in the strings
Trade-offs
Pros
Can handle any character set
More flexible than array approach
Clear and maintainable code
Cons
Higher memory overhead compared to array approach
Slightly slower due to HashMap operations
Use a single HashMap to store the first occurrence index of each character in both strings. Compare these indices to determine if the strings are isomorphic.
Algorithm
- Create two arrays to store last seen indices
- Iterate through both strings simultaneously
- For each character pair:
- Compare their last seen indices
- If indices don't match, return false
- Update last seen indices for both characters
- Return true if all indices match
Walkthrough
This approach uses a more efficient method by storing and comparing the first occurrence indices of characters in both strings. If two characters are mapped to each other, they must have the same first occurrence pattern throughout the strings.
public boolean isIsomorphic(String s, String t) { int[] lastSeenS = new int[256]; int[] lastSeenT = new int[256]; for (int i = 0; i < s.length(); i++) { char sChar = s.charAt(i); char tChar = t.charAt(i); // If current characters have different last seen indices, // strings cannot be isomorphic if (lastSeenS[sChar] != lastSeenT[tChar]) { return false; } // Update last seen index for both characters lastSeenS[sChar] = i + 1; lastSeenT[tChar] = i + 1; } return true;}Complexity
Time
O(n) where n is the length of the strings
Space
O(1) since we use fixed-size arrays
Trade-offs
Pros
Most efficient approach
Uses less memory than HashMap approach
Simpler logic with fewer comparisons
No need for bidirectional mapping checks
Cons
Limited to ASCII characters without modification
Might be less intuitive to understand at first glance
Solutions
Solution
public class Solution { public bool IsIsomorphic(string s, string t) { int[] d1 = new int[256]; int[] d2 = new int[256]; for (int i = 0; i < s.Length; ++i) { var a = s[i]; var b = t[i]; if (d1[a] != d2[b]) { return false; } d1[a] = i + 1; d2[b] = i + 1; } return true; }}class Solution {public boolean isIsomorphic(String s, String t) { int[] d1 = new int[256]; int[] d2 = new int[256]; int n = s.length(); for (int i = 0; i < n; ++i) { char a = s.charAt(i), b = t.charAt(i); if (d1[a] != d2[b]) { return false; } d1[a] = i + 1; d2[b] = i + 1; } return true; }}class Solution {public: bool isIsomorphic(string s, string t) { int d1[256]{}; int d2[256]{}; int n = s.size(); for (int i = 0; i < n; ++i) { char a = s[i], b = t[i]; if (d1[a] != d2[b]) { return false; } d1[a] = d2[b] = i + 1; } return true; }};class Solution: def isIsomorphic(self, s: str, t: str) -> bool: d1, d2 = [0] * 256, [0] * 256 for i, (a, b) in enumerate(zip(s, t), 1): a, b = ord(a), ord(b) if d1[a] != d2[b]: return False d1[a] = d2[b] = i return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.