Isomorphic Strings

Given two strings, determine if they are isomorphic.

Two strings X and Y are called isomorphic strings if all occurrences of each character in X can be replaced with another character to get Y and vice-versa.


For example,

Consider the strings "ACAB" and "XCXY". They are isomorphic as we can map 'A' -> 'X', 'B' -> 'Y' and 'C' -> 'C'.

Note that mapping from a character to itself is allowed but no two characters may be replaced by the same character.

Naive solution would be to check if every character in the first string is mapped to same character in the second string for all its occurrences. But even then two characters in first string might still be mapped to the same character in second string. So we have to repeat the process for second string as well. i.e. check if every character in second string is mapped to same character in first string for all its occurrences.

The time complexity of above solution is O(n2). We can improve time complexity to linear by using O(n) space.

The idea is to use Hashing. In the solution below, we use a map to store mapping from characters of string X to string Y and a set to store already mapped characters of string Y, rest of the code is pretty much straightforward.

Below is C++ and Java implementation of the idea –


Download   Run Code


Download   Run Code


ACAB and XCXY are Isomorphic

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of
Michael Keating

I think one could also make the value the map the distance between the two characters:

map[x] = x - y;

This way we don’t need to map y values.