Isomorphic string

Beginner Problems Basic Strings Easy

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:

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.

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

Output : false

Explanation : One possible try can be:

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 by this try. It can be proved that no solution exists for this example.

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

Constraints

1 <= s.length <= 10³
s.length == t.length
s and t consist of only lowercase English letters.

Company Tags

TCS Cognizant Accenture Infosys Capgemini Wipro IBM HCL Tech Mahindra MindTree

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/5SkCG9qxPfq/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Intuition:

To determine if two strings are isomorphic, the key insight is to recognize that two strings are isomorphic if the characters in one string can be replaced to get the other string. This can be efficiently checked by ensuring that there is a consistent mapping of characters from the first string to the second string and vice versa. The challenge lies in maintaining this mapping as the strings are traversed, ensuring that each character in the first string maps uniquely to a character in the second string, and that no two characters in the first string map to the same character in the second string.

Approach:

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.
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.
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.
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.

Dry Run:

Solution:

#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;
}
class Solution {
    public boolean isomorphicString(String s, String t) {
        // Arrays to store the last seen positions of characters in s and t
        int[] m1 = new int[256], m2 = new int[256];
        
        // Length of the string
        int n = s.length();
        
        // 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.charAt(i)] != m2[t.charAt(i)]) return false;
            
            // Update the last seen positions
            m1[s.charAt(i)] = i + 1;
            m2[t.charAt(i)] = i + 1;
        }
        
        // If all characters match, return true
        return true;
    }

    // Main method for testing
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "egg";
        String t = "add";
        if (solution.isomorphicString(s, t)) {
            System.out.println("Strings are isomorphic.");
        } else {
            System.out.println("Strings are not isomorphic.");
        }
    }
}
class Solution:
    def isomorphicString(self, s, t):
        # Arrays to store the last seen positions of characters in s and t
        m1, m2 = [0] * 256, [0] * 256
        
        # Length of the string
        n = len(s)
        
        # Iterate through each character in the strings
        for i in range(n):
            # If the last seen positions of the current characters don't match, return false
            if m1[ord(s[i])] != m2[ord(t[i])]:
                return False
            
            # Update the last seen positions
            m1[ord(s[i])] = i + 1
            m2[ord(t[i])] = i + 1
        
        # If all characters match, return true
        return True

# Main method for testing
if __name__ == "__main__":
    solution = Solution()
    s = "egg"
    t = "add"
    if solution.isomorphicString(s, t):
        print("Strings are isomorphic.")
    else:
        print("Strings are not isomorphic.")
class Solution {
    isomorphicString(s, t) {
        // Arrays to store the last seen positions of characters in s and t
        let m1 = Array(256).fill(0), m2 = Array(256).fill(0);
        
        // Length of the string
        let n = s.length;
        
        // Iterate through each character in the strings
        for (let i = 0; i < n; ++i) {
            // If the last seen positions of the current characters don't match, return false
            if (m1[s.charCodeAt(i)] !== m2[t.charCodeAt(i)]) return false;
            
            // Update the last seen positions
            m1[s.charCodeAt(i)] = i + 1;
            m2[t.charCodeAt(i)] = i + 1;
        }
        
        // If all characters match, return true
        return true;
    }
}

// Main method for testing
const solution = new Solution();
const s = "egg";
const t = "add";
if (solution.isomorphicString(s, t)) {
    console.log("Strings are isomorphic.");
} else {
    console.log("Strings are not isomorphic.");
}

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(k) O(1) since the space used by the arrays is constant (256 fixed size) regardless of input size

Code

Problem List