Isomorphic Strings

Problem: Given two strings s and t, determine if they are isomorphic. Two strings 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:

Input: s = "eef", t = "ggh"
Output: true

Input: s = "ab", t = "aa"
Output: false

Approach: We can use hash to maintain which character of s is mapped to which character to t and if we see that a same character of s is not getting mapped to same character of t, we can return false but this approach will fail in case of our second example (s = "ab", t = "aa"). Here is what will happen -

1. s[0] = 'a', t[0] = 'a',  'a' does not exist in hash so we will do hash['a'] = 'a'.
2. s[1] = 'b', t[1] = 'a' again 'b' does not exist in has so we will add 'b' in to hash; hash['b'] = 'a'.

So ultimately we will return true which is not correct as a and b both can't be replaced by a that mean we need reverse mapping too. Either we can maintain similar hash or we can just maintain a hashset which will tell us whether the current character of t is used before or not. That's all about the solution.

Implementation in C#:

    public bool IsIsomorphic(string s, string t)

    {

        int length = s?.Length ?? 0;

        if (length != t.Length)

        {

            return false;

        }

        var charMap = new Dictionary<char, char>();

        var usedChars = new HashSet<char>();

        for (int i = 0; i < length; ++i)

        {

            if (charMap.ContainsKey(s[i]))

            {

                if (charMap[s[i]] != t[i])

                {

                    return false;

                }

            }

            else

            {

                if (usedChars.Contains(t[i]))

                {

                    return false;

                }

                charMap[s[i]] = t[i];

                usedChars.Add(t[i]);

            }

        }

        return true;    

    }

Complexity: O(n)