1
00:00:00,600 --> 00:00:01,620
Welcome back.

2
00:00:01,620 --> 00:00:06,090
Let's now go ahead and code the solution which we discussed in the previous video.

3
00:00:06,120 --> 00:00:08,190
For this we are going to write a function.

4
00:00:08,190 --> 00:00:10,080
Let's call it max length.

5
00:00:10,620 --> 00:00:14,850
And this function is going to take in the string which is given to us.

6
00:00:15,480 --> 00:00:15,930
All right.

7
00:00:15,960 --> 00:00:20,430
Now inside this function let's have a variable which is called max.

8
00:00:20,430 --> 00:00:22,200
And let's initialize this to zero.

9
00:00:22,200 --> 00:00:26,970
So this is going to be the maximum length of the substring where the characters are unique.

10
00:00:26,970 --> 00:00:28,290
So we're going to find that.

11
00:00:28,290 --> 00:00:30,480
And finally we will return this value.

12
00:00:30,480 --> 00:00:32,490
So this is the function that we are trying to write.

13
00:00:32,850 --> 00:00:36,060
Now we will also need a variable called start.

14
00:00:36,060 --> 00:00:39,270
And initially this will point to the zeroth index right.

15
00:00:39,270 --> 00:00:45,420
And when we encounter a character which is repeating we will see whether we have to change the start

16
00:00:45,420 --> 00:00:46,080
or not.

17
00:00:46,080 --> 00:00:48,240
And we will need a hash table.

18
00:00:48,240 --> 00:00:49,650
Let's just call it scene.

19
00:00:49,650 --> 00:00:51,540
And initially it's empty.

20
00:00:51,600 --> 00:00:52,290
All right.

21
00:00:52,290 --> 00:00:54,900
Now we are going to traverse the string which is given to us.

22
00:00:54,900 --> 00:01:03,810
So let's use a for loop for let I is equal to zero I less than string dot length I plus plus.

23
00:01:05,320 --> 00:01:12,550
Right now at each index I we are going to take the character so we can say const char is equal to string

24
00:01:12,550 --> 00:01:13,150
at I.

25
00:01:13,240 --> 00:01:15,400
So we get that particular character.

26
00:01:15,400 --> 00:01:18,490
Now let's check whether it is there in the hash table.

27
00:01:18,490 --> 00:01:23,920
So if it's already there that means it occurred previously in the string which we are traversing.

28
00:01:23,920 --> 00:01:24,760
So let's check that.

29
00:01:24,760 --> 00:01:32,950
So if char in seen so if it's there in our hash table then we have to see whether we have to change

30
00:01:32,950 --> 00:01:34,210
the start or not.

31
00:01:34,210 --> 00:01:40,120
So we say start is equal to math dot max between start.

32
00:01:40,480 --> 00:01:47,740
That is the existing value of start and the value in the hash table for that particular character which

33
00:01:47,740 --> 00:01:49,780
is seen at char plus one.

34
00:01:49,780 --> 00:01:53,380
So we have to take the maximum among these two and set that to start.

35
00:01:53,380 --> 00:01:54,970
So what is happening over here.

36
00:01:54,970 --> 00:01:56,410
Let's take an example.

37
00:01:56,410 --> 00:02:01,390
Let's say the string which is given to us is a b c b d e f.

38
00:02:01,390 --> 00:02:08,410
Now when we encounter the second b, we will see that we have already entered b two our hash table.

39
00:02:08,410 --> 00:02:11,890
Again, we have not written the code for that, but we will be writing it below over here.

40
00:02:11,890 --> 00:02:12,340
All right.

41
00:02:12,340 --> 00:02:14,680
So we will make an entry.

42
00:02:16,080 --> 00:02:17,700
Into the hash table.

43
00:02:19,780 --> 00:02:21,100
If it's not there.

44
00:02:23,170 --> 00:02:24,310
So we are going to do that.

45
00:02:24,310 --> 00:02:26,680
So let's say we have already made this entry.

46
00:02:26,680 --> 00:02:29,950
And when we come to the second B we will find that it is already there.

47
00:02:29,950 --> 00:02:30,250
Right.

48
00:02:30,250 --> 00:02:35,050
So we cannot take this this substring to be consisting of unique characters.

49
00:02:35,050 --> 00:02:37,870
So we have to see whether we have to move the start point.

50
00:02:37,870 --> 00:02:41,710
And over here we can see that at this point the start is over here.

51
00:02:41,710 --> 00:02:42,310
Right.

52
00:02:42,310 --> 00:02:46,720
And this b the first B is occurring after the start happen.

53
00:02:46,720 --> 00:02:48,730
So we have to move the start to this place.

54
00:02:48,730 --> 00:02:50,440
So that is what we are checking over here.

55
00:02:50,440 --> 00:02:52,840
We are checking the maximum between zero.

56
00:02:52,840 --> 00:02:57,550
In this case start is at zero and then seen at char will be one right.

57
00:02:57,550 --> 00:03:00,190
That would be this index plus one which is two.

58
00:03:00,220 --> 00:03:02,800
So among zero and two two is the greater value.

59
00:03:02,800 --> 00:03:05,860
So for in this case we will move start to two.

60
00:03:05,860 --> 00:03:11,020
And then we will see how many characters we can take together to get the longest substring.

61
00:03:11,020 --> 00:03:13,750
And in this case it's going to be of length five right.

62
00:03:13,780 --> 00:03:15,460
C b d e and f.

63
00:03:15,460 --> 00:03:17,110
So that is what we are doing over here.

64
00:03:17,710 --> 00:03:24,580
Now once we have changed the start, if necessary we will go ahead and update our max value.

65
00:03:24,580 --> 00:03:24,760
Right?

66
00:03:24,760 --> 00:03:30,910
So Max is tracking the maximum length of the substring which is consisting of unique characters.

67
00:03:30,910 --> 00:03:37,360
So Max is going to be again the maximum math dot max between the existing value which is there in max,

68
00:03:37,360 --> 00:03:41,590
and the difference between I and start plus one.

69
00:03:42,280 --> 00:03:43,270
Why is that so?

70
00:03:43,300 --> 00:03:47,740
Let's take a look at our example over here a b c b d e f.

71
00:03:47,740 --> 00:03:51,040
Let's say we are at the second character over here.

72
00:03:51,040 --> 00:03:52,480
Now start is at zero.

73
00:03:52,480 --> 00:03:56,290
Now B the index where we are at right now is one.

74
00:03:56,290 --> 00:03:56,560
Right.

75
00:03:56,560 --> 00:04:04,540
So we can say that the the length of this substring AB is the index of b which is one minus start.

76
00:04:04,540 --> 00:04:07,240
So one -0 is equal to one plus one.

77
00:04:07,240 --> 00:04:09,940
So that's why we have I minus start plus one.

78
00:04:09,940 --> 00:04:14,620
Again we have this plus one over here because the indices start from zero over here.

79
00:04:14,620 --> 00:04:14,950
Right.

80
00:04:14,950 --> 00:04:19,360
So we are we are taking I is equal to zero initially and the indices are starting from zero.

81
00:04:19,360 --> 00:04:22,090
So that is why we are doing plus one over here.

82
00:04:22,090 --> 00:04:30,010
So this ensures that the length of the maximum substring with unique characters is stored to the max

83
00:04:30,010 --> 00:04:30,640
variable.

84
00:04:30,640 --> 00:04:37,690
And then we are just going to make an entry into our hash table if that particular character is not

85
00:04:37,690 --> 00:04:39,580
there as a key in our hash table.

86
00:04:39,580 --> 00:04:42,100
So let's do that scene at char.

87
00:04:43,280 --> 00:04:45,350
Is equal to I.

88
00:04:45,590 --> 00:04:46,850
Now there are two cases.

89
00:04:46,850 --> 00:04:48,320
If it's not there.

90
00:04:48,350 --> 00:04:51,440
Let's say for example, we are encountering B for the first time.

91
00:04:51,440 --> 00:04:53,240
It will not go to this place.

92
00:04:53,240 --> 00:04:59,120
And at this point it will make a fresh entry to our visited, uh, to our scene hash table.

93
00:04:59,150 --> 00:05:00,980
Now, if it's already there.

94
00:05:00,980 --> 00:05:05,510
And in that case, when we come over here, we are going to update the value.

95
00:05:05,510 --> 00:05:06,020
Right?

96
00:05:06,050 --> 00:05:12,080
We are going to update the value to the index where the particular character is occurring, the latest

97
00:05:12,080 --> 00:05:12,320
time.

98
00:05:12,320 --> 00:05:16,370
So for example let's again take this example and let's look at B.

99
00:05:16,370 --> 00:05:21,260
So over here we can see that B is first encountering is is coming up at index one.

100
00:05:21,260 --> 00:05:24,260
And then B is coming again at index three.

101
00:05:24,260 --> 00:05:24,410
Right.

102
00:05:24,410 --> 00:05:25,520
So this is index three.

103
00:05:25,520 --> 00:05:32,060
So initially in our scene hash table the value for key b will be one.

104
00:05:32,060 --> 00:05:36,020
But when we see the second b we will update the value to three.

105
00:05:36,020 --> 00:05:37,910
So that is what is happening over here.

106
00:05:37,910 --> 00:05:38,360
All right.

107
00:05:38,360 --> 00:05:39,320
So we are done.

108
00:05:39,320 --> 00:05:40,640
And that's it.

109
00:05:40,640 --> 00:05:42,410
So we are done with our function.

110
00:05:42,410 --> 00:05:43,370
So this should work.

111
00:05:43,370 --> 00:05:46,310
Now let's go ahead and test our function for this.

112
00:05:46,310 --> 00:05:47,540
Let's just try some.

113
00:05:48,330 --> 00:05:51,420
Strings, so I call the max length function.

114
00:05:52,410 --> 00:05:58,320
And let's say we pass a simple string a, b, c, d, and then let's have b.

115
00:05:58,680 --> 00:06:00,420
Now let's run it.

116
00:06:01,130 --> 00:06:05,600
Now we can see that we get the maximum length as four, which is correct.

117
00:06:05,600 --> 00:06:05,810
Right?

118
00:06:05,810 --> 00:06:10,790
So a b, c, d this is the maximum uh length of the substring.

119
00:06:10,790 --> 00:06:13,250
So this is the greatest substring with unique characters.

120
00:06:13,250 --> 00:06:15,500
And we can see that its length is four.

121
00:06:15,500 --> 00:06:18,680
Now what if we have something else over here.

122
00:06:18,680 --> 00:06:24,560
Let's just add some more, uh, uh, string characters over here.

123
00:06:25,780 --> 00:06:26,830
And let's run it.

124
00:06:26,830 --> 00:06:28,150
So we get ten over here.

125
00:06:28,150 --> 00:06:31,450
So definitely it's not this right.

126
00:06:31,450 --> 00:06:32,800
It should not start over here.

127
00:06:32,800 --> 00:06:34,690
So let's see this part over here.

128
00:06:34,690 --> 00:06:37,090
What's the length over here 123.

129
00:06:37,090 --> 00:06:38,800
And include we can include this B.

130
00:06:38,830 --> 00:06:40,000
We can include this C also.

131
00:06:40,000 --> 00:06:40,390
Right.

132
00:06:40,390 --> 00:06:43,390
So we just cannot include this B because there is a b over here.

133
00:06:43,390 --> 00:06:50,530
So let's look at this string 123456789 and ten.

134
00:06:50,530 --> 00:06:53,140
And we cannot take this D because we have a D over here.

135
00:06:53,140 --> 00:06:53,500
Right.

136
00:06:53,500 --> 00:06:55,090
So we cannot take this D.

137
00:06:55,090 --> 00:06:58,810
So we take this one over here and we can start over here.

138
00:06:58,810 --> 00:07:00,970
So this is the greatest substring right.

139
00:07:00,970 --> 00:07:02,050
The longest substring.

140
00:07:02,050 --> 00:07:06,730
So it has 3456789 and ten as the length.

141
00:07:06,730 --> 00:07:08,740
So yes our function is working.

142
00:07:08,740 --> 00:07:10,150
Let's just try one more thing.

143
00:07:10,150 --> 00:07:11,320
Let's just try one more.

144
00:07:11,320 --> 00:07:15,850
Let's say p q b r s t.

145
00:07:16,960 --> 00:07:18,430
Be you.

146
00:07:19,350 --> 00:07:20,760
VW.

147
00:07:22,780 --> 00:07:24,130
V x y.

148
00:07:24,160 --> 00:07:24,970
So let's see.

149
00:07:25,000 --> 00:07:28,360
And over here yes you can see we are getting the length seven which is correct.

150
00:07:28,360 --> 00:07:28,750
Right.

151
00:07:28,750 --> 00:07:33,850
So that's starting over here we have 3456 and seven.

152
00:07:33,850 --> 00:07:37,090
So this is the greatest substring with unique characters.

153
00:07:37,090 --> 00:07:38,650
And the length of it is seven.

154
00:07:38,650 --> 00:07:40,300
So our function is working.

155
00:07:40,300 --> 00:07:46,390
Now let's take a sample input and again run through the code and see what's happening.

156
00:07:46,390 --> 00:07:50,590
And let's also relook at the space and time complexity of our solution.