1
00:00:00,670 --> 00:00:01,780
Welcome back.

2
00:00:01,780 --> 00:00:05,470
Let's now try to understand how we can solve this question.

3
00:00:05,470 --> 00:00:12,130
Now there there could be a naive method, right, which has a time complexity of O of n square, which

4
00:00:12,130 --> 00:00:13,420
is the brute force method.

5
00:00:13,420 --> 00:00:14,350
How would we do it?

6
00:00:14,350 --> 00:00:21,220
We would just take every character in S, and then we will loop through S and T for that particular

7
00:00:21,220 --> 00:00:21,820
character.

8
00:00:21,820 --> 00:00:22,210
Right.

9
00:00:22,210 --> 00:00:27,970
And then we are going to check whether the same character is mapped to the same character in T always.

10
00:00:27,970 --> 00:00:32,680
And we will check whether no other character is mapped with that particular mapping.

11
00:00:32,680 --> 00:00:33,550
So what do I mean?

12
00:00:33,550 --> 00:00:34,960
Let's just take an example.

13
00:00:34,960 --> 00:00:44,860
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.

14
00:00:44,860 --> 00:00:50,260
So we know that these two are not isomorphic because A is mapped to p and d is also mapped to p.

15
00:00:50,290 --> 00:00:50,620
Right.

16
00:00:50,620 --> 00:00:52,390
So we know it's not isomorphic.

17
00:00:52,390 --> 00:00:54,430
Let's take one more case for example.

18
00:00:54,430 --> 00:00:58,930
Let's have over here um C itself and let's map it to.

19
00:00:59,800 --> 00:01:05,620
Oh, now, as per the naive method or the brute force method, we'll just take every character in S.

20
00:01:05,620 --> 00:01:12,670
For example, we take a and then we loop through a, b, c, D, c to check whether A is happening again.

21
00:01:12,670 --> 00:01:13,030
Right.

22
00:01:13,030 --> 00:01:16,570
And if it's happening we would have checked whether it's mapped to P.

23
00:01:16,570 --> 00:01:18,250
So in this case it's not there.

24
00:01:18,250 --> 00:01:18,730
All right.

25
00:01:18,730 --> 00:01:20,740
And then we are going to check again.

26
00:01:20,740 --> 00:01:21,970
We have P over here.

27
00:01:21,970 --> 00:01:25,300
Now as we go through we are going to check whether we get P also.

28
00:01:25,300 --> 00:01:25,660
Right.

29
00:01:25,660 --> 00:01:29,830
And if we get P we have to check back whether over here it's A or not.

30
00:01:29,830 --> 00:01:32,170
So that is what we are going to do over here.

31
00:01:32,170 --> 00:01:38,110
And for example, when we take the character C again we are going to loop through the uh string over

32
00:01:38,110 --> 00:01:38,410
here.

33
00:01:38,410 --> 00:01:43,450
And we are going to check whether, if this is, ah, every other occurrence of C is ah.

34
00:01:43,450 --> 00:01:49,300
And if you have ah in the second string, whether it's mapped to something else other than C in the

35
00:01:49,300 --> 00:01:49,780
first string.

36
00:01:49,780 --> 00:01:50,050
Right.

37
00:01:50,050 --> 00:01:51,940
So that is the brute force method.

38
00:01:51,940 --> 00:01:56,590
Right now you can see that there is a lot of operations to be done if you do it in this manner.

39
00:01:56,590 --> 00:01:59,620
That's why the time complexity over here will be O of n square.

40
00:01:59,620 --> 00:02:00,280
Why is that.

41
00:02:00,280 --> 00:02:03,430
So we have n characters let's say in string s.

42
00:02:03,430 --> 00:02:08,470
And for each of these characters we have to do n operations which is looping through.

43
00:02:08,470 --> 00:02:10,420
And then we are doing some constant operations.

44
00:02:10,420 --> 00:02:10,720
Right.

45
00:02:10,720 --> 00:02:16,180
So we are going to check whether the mapping from S to T is isomorphic.

46
00:02:16,180 --> 00:02:20,380
And then we are going to check whether the mapping from T to S is isomorphic.

47
00:02:20,380 --> 00:02:20,650
Right.

48
00:02:20,650 --> 00:02:23,200
So again that's n operations.

49
00:02:23,200 --> 00:02:26,140
And in each operation some constant time operations.

50
00:02:26,140 --> 00:02:27,100
So n into n.

51
00:02:27,100 --> 00:02:29,860
That gives us a time complexity of O of n square.

52
00:02:29,860 --> 00:02:31,540
Now we are not going to code this.

53
00:02:31,540 --> 00:02:36,040
Let's go ahead and look at the optimal solution or how to do this in a better manner.

54
00:02:36,040 --> 00:02:40,780
Let's say the two given strings over here are green and ABCd.

55
00:02:41,440 --> 00:02:46,960
Now let's try to think through how we can solve this in an efficient manner with this example.

56
00:02:46,960 --> 00:02:53,260
The first thing is that if these two strings are not of the same length, then we can just return false,

57
00:02:53,260 --> 00:02:53,500
right?

58
00:02:53,500 --> 00:02:57,160
Because there will be some character which is not mapped to some anything.

59
00:02:57,160 --> 00:02:58,270
So that is not allowed.

60
00:02:58,270 --> 00:03:00,730
If the two strings should be isomorphic.

61
00:03:00,730 --> 00:03:04,300
So if the lengths are not equal, we can just return false.

62
00:03:04,300 --> 00:03:08,470
Now if the lengths are equal we are going to have two hash maps.

63
00:03:08,470 --> 00:03:11,260
Let's call it's hash and t hash.

64
00:03:11,260 --> 00:03:13,120
And initially they are empty.

65
00:03:13,150 --> 00:03:17,980
Now we are going to loop through the the two strings together.

66
00:03:17,980 --> 00:03:20,470
Right now we know that these two are of same length.

67
00:03:20,470 --> 00:03:25,150
So in this case we are going to take the values of I from 0 to 4.

68
00:03:25,150 --> 00:03:25,690
So this.

69
00:03:25,690 --> 00:03:26,500
So this is zero.

70
00:03:26,500 --> 00:03:29,020
This is 123 and four.

71
00:03:29,020 --> 00:03:32,110
So we are going to iterate through these values right.

72
00:03:32,110 --> 00:03:35,170
So for I is equal to zero till four.

73
00:03:35,320 --> 00:03:39,760
Now we are going to iterate it iterate through the two given strings.

74
00:03:39,760 --> 00:03:43,360
Now when I is equal to zero we are going to take these two characters.

75
00:03:43,360 --> 00:03:45,700
That's G over here and A over here.

76
00:03:45,700 --> 00:03:51,970
Now we are going to check whether there is any mapping for G in S hash, which is not there at this

77
00:03:51,970 --> 00:03:52,240
point.

78
00:03:52,240 --> 00:03:52,570
Right.

79
00:03:52,570 --> 00:03:55,720
So we are going to make an entry in S hash.

80
00:03:55,720 --> 00:03:58,600
And the value is going to be a over here.

81
00:03:58,600 --> 00:04:04,720
Similarly in t hash we are going to make an entry where the key is a and the value is g.

82
00:04:04,720 --> 00:04:10,450
So we are making these two mappings over here right from G to A over here and from A to G over here.

83
00:04:10,450 --> 00:04:12,100
That's for I is equal to zero.

84
00:04:12,100 --> 00:04:14,080
Now I change this to one.

85
00:04:14,080 --> 00:04:18,520
So when I is equal to one we are going to have r over here and b over here.

86
00:04:18,520 --> 00:04:18,820
Right.

87
00:04:18,820 --> 00:04:21,580
And then we are checking whether R is over there in S hash.

88
00:04:21,580 --> 00:04:22,330
It's not there.

89
00:04:22,330 --> 00:04:23,680
So we make an entry.

90
00:04:23,680 --> 00:04:25,420
The keys are the value is b.

91
00:04:25,420 --> 00:04:27,670
We are going to check whether B is there in t hash.

92
00:04:27,670 --> 00:04:28,450
It's not there.

93
00:04:28,450 --> 00:04:30,910
So we are making an entry from B to r.

94
00:04:30,940 --> 00:04:32,950
The key is b the value is r.

95
00:04:32,980 --> 00:04:36,010
Now again I change I is incremented I becomes two.

96
00:04:36,040 --> 00:04:40,570
We get E and we get C, and we see that e is not there in S hash.

97
00:04:40,570 --> 00:04:41,050
Right.

98
00:04:41,050 --> 00:04:43,060
So we make an entry e and c.

99
00:04:43,090 --> 00:04:45,130
Similarly c is not there in t hash.

100
00:04:45,130 --> 00:04:48,640
So we make an entry c and e the key c the value is e.

101
00:04:48,730 --> 00:04:51,040
Now again I is incremented to three.

102
00:04:51,040 --> 00:04:53,740
And we get to e over here and see over here.

103
00:04:53,740 --> 00:04:59,020
Right now we are going to check whether we have E in S it's there right.

104
00:04:59,020 --> 00:05:05,020
And the value of that is C which is correct as per what we have over here right in the two strings.

105
00:05:05,020 --> 00:05:07,540
So as per this the criteria is met.

106
00:05:08,020 --> 00:05:11,020
Now we are going to check whether C is there in t hash.

107
00:05:11,020 --> 00:05:16,270
We see it's there and the mapping is to E over here in the hash table.

108
00:05:16,270 --> 00:05:18,040
And we have E over here as well.

109
00:05:18,040 --> 00:05:21,790
So yes as per this mapping also this is true right now.

110
00:05:21,790 --> 00:05:23,380
Therefore we proceed.

111
00:05:23,380 --> 00:05:26,350
Now again we go from to I equal to four.

112
00:05:26,350 --> 00:05:29,800
We have n and d over here we make the entry in d and d n.

113
00:05:29,800 --> 00:05:34,870
So as per this we see that we do not see any inconsistency.

114
00:05:34,870 --> 00:05:37,630
Therefore these two strings are isomorphic.

115
00:05:37,630 --> 00:05:43,210
Now let's also take a look at two false cases to understand how this algorithm works.

116
00:05:43,210 --> 00:05:44,920
So let's make some space over here.

117
00:05:44,920 --> 00:05:48,280
Now let's say s is a and t is BC.

118
00:05:48,310 --> 00:05:50,890
We know that these two are not isomorphic, right.

119
00:05:50,890 --> 00:05:54,250
Because A is mapped to B over here and A is mapped to C over here.

120
00:05:54,250 --> 00:05:56,980
But let's see how the algorithm tackles this.

121
00:05:56,980 --> 00:05:59,080
Initially we are going to get A and B.

122
00:05:59,350 --> 00:06:00,640
Right when I is equal to zero.

123
00:06:00,640 --> 00:06:03,250
So and our hash tables are going to be empty.

124
00:06:03,250 --> 00:06:08,320
So we make an entry a key is a and value is b over here in S hash.

125
00:06:08,320 --> 00:06:10,360
And the key is b in t hash.

126
00:06:10,360 --> 00:06:11,410
And the value is a.

127
00:06:11,440 --> 00:06:14,290
Now we increment I and we get a and c.

128
00:06:14,320 --> 00:06:18,970
Right now we see that yes a is there in S hash.

129
00:06:18,970 --> 00:06:20,890
But we are going to check the value.

130
00:06:20,890 --> 00:06:22,180
The value over here is b.

131
00:06:22,180 --> 00:06:23,980
But over here we have c right.

132
00:06:23,980 --> 00:06:28,690
So as per this mapping this is not isomorphic with what we have over here.

133
00:06:28,690 --> 00:06:32,680
So we identify that these two strings are not isomorphic.

134
00:06:32,680 --> 00:06:33,910
And we return false.

135
00:06:33,910 --> 00:06:40,240
Now let's take one more look let's say and again after this we will end the the algorithm will go ahead

136
00:06:40,240 --> 00:06:42,130
and make this entry because C is not there.

137
00:06:42,130 --> 00:06:43,630
Over here we write C a.

138
00:06:43,630 --> 00:06:46,060
But again we were able to identify it's false.

139
00:06:46,060 --> 00:06:47,350
Now let's proceed.

140
00:06:47,350 --> 00:06:50,950
Let's say s is equal to a b and t is equal to c c.

141
00:06:50,950 --> 00:06:56,440
Right now in this case also we know that these two strings are not isomorphic because A is also mapped

142
00:06:56,440 --> 00:06:58,480
to C and B is also mapped to c.

143
00:06:58,510 --> 00:07:00,910
Now let's see how the algorithm tackles this.

144
00:07:00,910 --> 00:07:03,580
Initially when I is equal to zero we have a and c.

145
00:07:03,580 --> 00:07:06,190
So we make the entries in S and t hash.

146
00:07:06,190 --> 00:07:08,410
We have a c and we have c a.

147
00:07:08,440 --> 00:07:12,430
Now I is incremented and we get b over here and we get C over here.

148
00:07:12,430 --> 00:07:16,150
Now we look at S hash and we see that B is not there over here.

149
00:07:16,150 --> 00:07:18,280
So we make an entry b c over here.

150
00:07:18,280 --> 00:07:23,980
Now at this point we have not identified the the two strings not to be isomorphic.

151
00:07:23,980 --> 00:07:27,670
But after this we are going to check whether C is there in T hash.

152
00:07:27,670 --> 00:07:28,780
And we see it's there.

153
00:07:28,780 --> 00:07:29,110
Right.

154
00:07:29,110 --> 00:07:30,250
So we see it's there.

155
00:07:30,250 --> 00:07:32,020
And the value over here is a.

156
00:07:32,020 --> 00:07:33,880
But over here C is mapped to B.

157
00:07:33,880 --> 00:07:34,210
Right.

158
00:07:34,210 --> 00:07:36,820
So we identify that this criteria fails.

159
00:07:36,820 --> 00:07:39,820
And hence we are able to identify that this is false.

160
00:07:39,820 --> 00:07:41,860
So this is how the algorithm works.

161
00:07:41,860 --> 00:07:42,190
Right.

162
00:07:42,190 --> 00:07:46,690
We are going to check we are going to iterate through the strings given together.

163
00:07:46,690 --> 00:07:52,720
And we are going to make entries into the assertion to hash tables if entries are not already there.

164
00:07:52,720 --> 00:07:58,240
And if entries are there, then we are going to see whether the particular instance where we have the

165
00:07:58,240 --> 00:08:01,960
two characters follows what is entered in the hash tables.

166
00:08:01,960 --> 00:08:06,220
So this is how we are solving this problem in an optimum manner.

167
00:08:06,220 --> 00:08:09,580
Now let's look at the time and space complexity of this solution.

168
00:08:09,580 --> 00:08:15,370
The time complexity of the solution is O of n, because we are just going through the strings once,

169
00:08:15,370 --> 00:08:17,320
right where n is the length of the string, right?

170
00:08:17,320 --> 00:08:18,640
So n is the length of the string.

171
00:08:18,640 --> 00:08:23,200
And we know that the lengths have to be equal and we are just traversing each string once.

172
00:08:23,200 --> 00:08:26,950
So that's why the time complexity of this solution is O of n.

173
00:08:26,950 --> 00:08:30,370
And the space complexity is a bit tricky over here.

174
00:08:30,370 --> 00:08:36,370
The space complexity is O of one, because in the question it's mentioned that the strings are made

175
00:08:36,370 --> 00:08:38,890
up of valid Ascii characters.

176
00:08:38,890 --> 00:08:43,240
Now, valid Ascii characters is a fixed size set, right?

177
00:08:43,240 --> 00:08:43,840
So there is a.

178
00:08:43,840 --> 00:08:47,410
There is a maximum possibility of 128 Ascii characters.

179
00:08:47,410 --> 00:08:47,710
Right.

180
00:08:47,710 --> 00:08:55,390
So even if we make these two hash tables, the maximum possible size that they can grow up to is 128

181
00:08:55,390 --> 00:08:57,940
into two, which is 256, which is a constant.

182
00:08:57,940 --> 00:08:58,240
Right.

183
00:08:58,240 --> 00:09:01,360
So O of 256 is nothing but O of one.

184
00:09:01,360 --> 00:09:07,930
That is why we find that the space complexity of this solution is O of one, or this solution runs in

185
00:09:07,930 --> 00:09:08,920
constant space.

186
00:09:08,920 --> 00:09:14,800
That is, as we keep increasing the length of the strings right the length of the strings as it keeps

187
00:09:14,800 --> 00:09:19,450
increasing the space complexity will not increase in any proportion.

188
00:09:19,450 --> 00:09:20,620
It will remain constant.

189
00:09:20,620 --> 00:09:22,750
The maximum will be 256, right?

190
00:09:22,750 --> 00:09:27,670
It will be maximum something into 256, constant into 256.

191
00:09:27,670 --> 00:09:32,230
And we know that space complexity of a constant is nothing but O of one.