Welcome back.
Let's now try to understand how we can solve this question.
Now there there could be a naive method, right, which has a time complexity of O of n square, which
is the brute force method.
How would we do it?
We would just take every character in S, and then we will loop through S and T for that particular
character.
Right.
And then we are going to check whether the same character is mapped to the same character in T always.
And we will check whether no other character is mapped with that particular mapping.
So what do I mean?
Let's just take an example.
Let's say s is A, B, C, and d, and let's say t is um, let's let's take it as p, q, r and p.
So we know that these two are not isomorphic because A is mapped to p and d is also mapped to p.
Right.
So we know it's not isomorphic.
Let's take one more case for example.
Let's have over here um C itself and let's map it to.
Oh, now, as per the naive method or the brute force method, we'll just take every character in S.
For example, we take a and then we loop through a, b, c, D, c to check whether A is happening again.
Right.
And if it's happening we would have checked whether it's mapped to P.
So in this case it's not there.
All right.
And then we are going to check again.
We have P over here.
Now as we go through we are going to check whether we get P also.
Right.
And if we get P we have to check back whether over here it's A or not.
So that is what we are going to do over here.
And for example, when we take the character C again we are going to loop through the uh string over
here.
And we are going to check whether, if this is, ah, every other occurrence of C is ah.
And if you have ah in the second string, whether it's mapped to something else other than C in the
first string.
Right.
So that is the brute force method.
Right now you can see that there is a lot of operations to be done if you do it in this manner.
That's why the time complexity over here will be O of n square.
Why is that.
So we have n characters let's say in string s.
And for each of these characters we have to do n operations which is looping through.
And then we are doing some constant operations.
Right.
So we are going to check whether the mapping from S to T is isomorphic.
And then we are going to check whether the mapping from T to S is isomorphic.
Right.
So again that's n operations.
And in each operation some constant time operations.
So n into n.
That gives us a time complexity of O of n square.
Now we are not going to code this.
Let's go ahead and look at the optimal solution or how to do this in a better manner.
Let's say the two given strings over here are green and ABCd.
Now let's try to think through how we can solve this in an efficient manner with this example.
The first thing is that if these two strings are not of the same length, then we can just return false,
right?
Because there will be some character which is not mapped to some anything.
So that is not allowed.
If the two strings should be isomorphic.
So if the lengths are not equal, we can just return false.
Now if the lengths are equal we are going to have two hash maps.
Let's call it's hash and t hash.
And initially they are empty.
Now we are going to loop through the the two strings together.
Right now we know that these two are of same length.
So in this case we are going to take the values of I from 0 to 4.
So this.
So this is zero.
This is 123 and four.
So we are going to iterate through these values right.
So for I is equal to zero till four.
Now we are going to iterate it iterate through the two given strings.
Now when I is equal to zero we are going to take these two characters.
That's G over here and A over here.
Now we are going to check whether there is any mapping for G in S hash, which is not there at this
point.
Right.
So we are going to make an entry in S hash.
And the value is going to be a over here.
Similarly in t hash we are going to make an entry where the key is a and the value is g.
So we are making these two mappings over here right from G to A over here and from A to G over here.
That's for I is equal to zero.
Now I change this to one.
So when I is equal to one we are going to have r over here and b over here.
Right.
And then we are checking whether R is over there in S hash.
It's not there.
So we make an entry.
The keys are the value is b.
We are going to check whether B is there in t hash.
It's not there.
So we are making an entry from B to r.
The key is b the value is r.
Now again I change I is incremented I becomes two.
We get E and we get C, and we see that e is not there in S hash.
Right.
So we make an entry e and c.
Similarly c is not there in t hash.
So we make an entry c and e the key c the value is e.
Now again I is incremented to three.
And we get to e over here and see over here.
Right now we are going to check whether we have E in S it's there right.
And the value of that is C which is correct as per what we have over here right in the two strings.
So as per this the criteria is met.
Now we are going to check whether C is there in t hash.
We see it's there and the mapping is to E over here in the hash table.
And we have E over here as well.
So yes as per this mapping also this is true right now.
Therefore we proceed.
Now again we go from to I equal to four.
We have n and d over here we make the entry in d and d n.
So as per this we see that we do not see any inconsistency.
Therefore these two strings are isomorphic.
Now let's also take a look at two false cases to understand how this algorithm works.
So let's make some space over here.
Now let's say s is a and t is BC.
We know that these two are not isomorphic, right.
Because A is mapped to B over here and A is mapped to C over here.
But let's see how the algorithm tackles this.
Initially we are going to get A and B.
Right when I is equal to zero.
So and our hash tables are going to be empty.
So we make an entry a key is a and value is b over here in S hash.
And the key is b in t hash.
And the value is a.
Now we increment I and we get a and c.
Right now we see that yes a is there in S hash.
But we are going to check the value.
The value over here is b.
But over here we have c right.
So as per this mapping this is not isomorphic with what we have over here.
So we identify that these two strings are not isomorphic.
And we return false.
Now let's take one more look let's say and again after this we will end the the algorithm will go ahead
and make this entry because C is not there.
Over here we write C a.
But again we were able to identify it's false.
Now let's proceed.
Let's say s is equal to a b and t is equal to c c.
Right now in this case also we know that these two strings are not isomorphic because A is also mapped
to C and B is also mapped to c.
Now let's see how the algorithm tackles this.
Initially when I is equal to zero we have a and c.
So we make the entries in S and t hash.
We have a c and we have c a.
Now I is incremented and we get b over here and we get C over here.
Now we look at S hash and we see that B is not there over here.
So we make an entry b c over here.
Now at this point we have not identified the the two strings not to be isomorphic.
But after this we are going to check whether C is there in T hash.
And we see it's there.
Right.
So we see it's there.
And the value over here is a.
But over here C is mapped to B.
Right.
So we identify that this criteria fails.
And hence we are able to identify that this is false.
So this is how the algorithm works.
Right.
We are going to check we are going to iterate through the strings given together.
And we are going to make entries into the assertion to hash tables if entries are not already there.
And if entries are there, then we are going to see whether the particular instance where we have the
two characters follows what is entered in the hash tables.
So this is how we are solving this problem in an optimum manner.
Now let's look at the time and space complexity of this solution.
The time complexity of the solution is O of n, because we are just going through the strings once,
right where n is the length of the string, right?
So n is the length of the string.
And we know that the lengths have to be equal and we are just traversing each string once.
So that's why the time complexity of this solution is O of n.
And the space complexity is a bit tricky over here.
The space complexity is O of one, because in the question it's mentioned that the strings are made
up of valid Ascii characters.
Now, valid Ascii characters is a fixed size set, right?
So there is a.
There is a maximum possibility of 128 Ascii characters.
Right.
So even if we make these two hash tables, the maximum possible size that they can grow up to is 128
into two, which is 256, which is a constant.
Right.
So O of 256 is nothing but O of one.
That is why we find that the space complexity of this solution is O of one, or this solution runs in
constant space.
That is, as we keep increasing the length of the strings right the length of the strings as it keeps
increasing the space complexity will not increase in any proportion.
It will remain constant.
The maximum will be 256, right?
It will be maximum something into 256, constant into 256.
And we know that space complexity of a constant is nothing but O of one.