Problem Statement

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.

Examples

Example 1

Input : s = "egg" , t = "add"
Output : true

Explanation : The 'e' in string s can be replaced with 'a' of string t.

The 'g' in string s can be replaced with 'd' of t.

Hence all characters in s can be replaced to get t.

Example 2

Input : s = "apple" , t = "bbnbm"
Output : false

Explanation : The 'a' in string s can be replaced with 'n' of string t.

The 'p' in string s can be replaced by 'b' of string t.

The 'l' in string s can be replaced by 'm' of string t.

The 'e' in string s cannot be replaced by any character of string t as all the characters in string t are already mapped.

Hence all characters in s cannot be replaced to get t.

Example 3

Input : s = "paper" , t = "title"
Output :
true

Example 4

Inpur: s = "foo", t = "bar"
Output: false

'f' should map to 'b'
'o' should map to 'a'
and then again
'o' map to 'r' which is inconsistent.

Constraints

• 1 <= s.length <= 103
• s.length == t.length
• s and t consist of only lowercase English letters.

Approaches

1️⃣ Using Array

Approach:

1. Initialize two arrays of size 256 (to cover all ASCII characters) to store the last seen positions of characters in both strings. This helps in tracking the mapping between characters.
2. Iterate through each character in the strings simultaneously. For each character, compare the last seen positions stored in the arrays. If the positions do not match, it indicates an inconsistent mapping, and the strings are not isomorphic.
3. If the positions match, update the arrays with the current index (incremented by 1 to avoid the default value of 0). This ensures that the mapping is consistent throughout the strings.
4. After completing the iteration, if no inconsistencies in the mappings are found, the strings are confirmed to be isomorphic. If any inconsistency is found during the iteration, return false immediately.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isomorphicString(string s, string t) {
        // Arrays to store the last seen positions of characters in s and t
        int m1[256] = {0}, m2[256] = {0}; 
        
        // Length of the string
        int n = s.size(); 
        
        // Iterate through each character in the strings
        for (int i = 0; i < n; ++i) {
            // If the last seen positions of the current characters don't match, return false
            if (m1[s[i]] != m2[t[i]]) return false;
            
            // Update the last seen positions
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        
        // If all characters match, return true
        return true;
    }
};

// Main method for testing
int main() {
    Solution solution;
    string s = "egg";
    string t = "add";
    if (solution.isomorphicString(s, t)) {
        cout << "Strings are isomorphic." << endl;
    } else {
        cout << "Strings are not isomorphic." << endl;
    }
    return 0;
}

Step-by-Step Iteration:

For example: s = “foo”, t = “bar”

m1[256] and m2[256] are initialized to 0.

The length of the string n = 3

1 Iteration 1 (i = 0):

• Characters:s[0] = 'f', t[0] = 'b'.
• Check Last Seen Positions:
  • m1['f'] is 0 (hasn't been seen before).
  • m2['b'] is 0 (hasn't been seen before).
• Positions match (0 == 0), so continue.
• Update Last Seen Positions:
  • m1['f'] = 1, m2['b'] = 1.

2 Iteration 2 (i = 1):

• Characters:s[1] = 'o', t[1] = 'a'.
• Check Last Seen Positions:
  • m1['o'] is 0 (hasn't been seen before).
  • m2['a'] is 0 (hasn't been seen before).
• Positions match (0 == 0), so continue.
• Update Last Seen Positions:
  • m1['o'] = 2, m2['a'] = 2.

3 Iteration 3 (i = 2):

• Characters:s[2] = 'o', t[2] = 'r'.
• Check Last Seen Positions:
  • m1['o'] is 2 (seen previously at index 1).
  • m2['r'] is 0 (hasn't been seen before).
• Mismatch Found: m1['o'] != m2['r'] (2 != 0), so return false.

Complexity Analysis:

• Time Complexity:O(N) where N is the length of the input strings, due to the single loop iterating through each character.
• Space Complexity:O(1) since the space used by the arrays is constant (256 fixed size) regardless of input size.