# Isomorphic Strings
**Difficulty:** EASY
[External](https://leetcode.com/problems/isomorphic-strings)
Canonical: https://scaleengineer.com/dsa/problems/isomorphic-strings
**Data structures:** Hash Table, String
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Google](https://scaleengineer.com/companies/google), [Infosys](https://scaleengineer.com/companies/infosys), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Oracle](https://scaleengineer.com/companies/oracle), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Salesforce](https://scaleengineer.com/companies/salesforce), [HashedIn](https://scaleengineer.com/companies/hashedin), [Remitly](https://scaleengineer.com/companies/remitly)
---
## Problem
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 * 104`
* `t.length == s.length`
* `s` and `t` consist of any valid ascii character.

# Approaches
## Character Array Mapping
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.
**Time:** O(n) where n is the length of the strings · **Space:** O(1) since we use fixed-size arrays of 256 characters
**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
### Explanation
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.

```java
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;
}
```
### Algorithm
1. Create two character arrays sToT and tToS of size 256
2. Iterate through both strings simultaneously
3. 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
4. Return true if all mappings are consistent

## HashMap Approach
Use two HashMaps to store the character mappings between the strings. This approach is more flexible and can handle any character set.
**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
**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
### Explanation
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.

```java
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;
}
```
### Algorithm
1. Create two HashMaps for storing mappings from s to t and t to s
2. Iterate through both strings simultaneously
3. 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
4. Return true if all mappings are consistent

## Single Map with Character Indexing
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.
**Time:** O(n) where n is the length of the strings · **Space:** O(1) since we use fixed-size arrays
**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
### Explanation
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.

```java
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;
}
```
### Algorithm
1. Create two arrays to store last seen indices
2. Iterate through both strings simultaneously
3. For each character pair:
   - Compare their last seen indices
   - If indices don't match, return false
   - Update last seen indices for both characters
4. Return true if all indices match

# Solutions
### CSharp

```csharp
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;
    }
}
```

### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 True

```