1 00:00:00,680 --> 00:00:01,700 Welcome back. 2 00:00:01,700 --> 00:00:04,190 So this is the code that we have just now written. 3 00:00:04,220 --> 00:00:10,040 Now let's take a sample input and walk through the code and see what's happening at each line over here. 4 00:00:10,040 --> 00:00:16,970 Now let's say the string which is passed to the function is a b c b d e f. 5 00:00:16,970 --> 00:00:17,450 All right. 6 00:00:17,450 --> 00:00:19,790 Now let's say this is the string which is passed to it. 7 00:00:19,790 --> 00:00:25,460 Now initially once we are inside the function max is set to zero and start is pointing to zero. 8 00:00:25,460 --> 00:00:25,760 Right? 9 00:00:25,760 --> 00:00:27,140 Start is equal to zero. 10 00:00:27,140 --> 00:00:30,380 And then we have our hash table seen which is empty. 11 00:00:30,380 --> 00:00:31,610 So seen. 12 00:00:31,610 --> 00:00:34,700 Let me just write this over here C is empty at this point. 13 00:00:35,060 --> 00:00:38,930 Now we are going to loop through the string which is given to us. 14 00:00:38,930 --> 00:00:40,640 Initially I is equal to zero. 15 00:00:40,640 --> 00:00:43,850 We take the character at string zero which is a right. 16 00:00:43,850 --> 00:00:47,930 So this is zero, one, two, three, four, five and six. 17 00:00:47,930 --> 00:00:49,070 So these are the indices. 18 00:00:49,070 --> 00:00:50,150 So we take a. 19 00:00:50,180 --> 00:00:53,150 Now we are checking whether A is there in seen it's not. 20 00:00:53,150 --> 00:00:55,220 So we are going to make a mapping right. 21 00:00:55,220 --> 00:00:56,870 So again that's happening over here. 22 00:00:56,870 --> 00:00:58,010 We are checking whether it's there. 23 00:00:58,010 --> 00:00:59,000 It's not there. 24 00:00:59,000 --> 00:01:01,280 So we are going to update Max. 25 00:01:01,280 --> 00:01:06,410 Now Max at this point is zero I is equal to zero at this point right. 26 00:01:07,040 --> 00:01:08,240 And start is zero. 27 00:01:08,240 --> 00:01:09,830 So zero -0 plus one. 28 00:01:09,830 --> 00:01:12,050 So the max is zero. 29 00:01:12,050 --> 00:01:13,880 And this part over here becomes one. 30 00:01:13,880 --> 00:01:16,250 Now the maximum among zero and one is one. 31 00:01:16,250 --> 00:01:18,380 So Max is updated to one. 32 00:01:18,380 --> 00:01:20,690 At this point let me just track it over here itself. 33 00:01:20,690 --> 00:01:23,300 Or or probably I can just do it at this side. 34 00:01:23,300 --> 00:01:24,770 So let me just wrap this. 35 00:01:24,770 --> 00:01:26,420 And over here I'll track Max. 36 00:01:26,420 --> 00:01:28,970 So we have seen that Max has become one. 37 00:01:29,120 --> 00:01:37,040 Now at this part we are going to make an entry into our scene hash table and scene at car. 38 00:01:37,040 --> 00:01:40,970 Right char the the key is going to be the character which is a. 39 00:01:40,970 --> 00:01:45,050 So the key is a and the value is going to be the index, which is zero. 40 00:01:45,050 --> 00:01:46,580 At this point the index is zero. 41 00:01:46,580 --> 00:01:50,060 Again we increment I, so I becomes one. 42 00:01:50,060 --> 00:01:52,850 Now we take the character at index one which is b. 43 00:01:52,880 --> 00:01:54,920 Now we are going to check whether B is in C. 44 00:01:54,920 --> 00:01:56,030 No it's not there. 45 00:01:56,030 --> 00:01:58,160 So again we're going to update max right. 46 00:01:58,160 --> 00:02:02,180 So max at this point is one and I is equal to one. 47 00:02:02,180 --> 00:02:05,150 So one -0 is one one plus one is two. 48 00:02:05,180 --> 00:02:08,030 So among one and two two is the greater value. 49 00:02:08,030 --> 00:02:09,890 So we update max to two. 50 00:02:09,890 --> 00:02:11,870 And we are going to make an entry right. 51 00:02:11,870 --> 00:02:16,100 So the key is going to be B and the value is going to be one. 52 00:02:16,100 --> 00:02:17,540 Again I is incremented. 53 00:02:17,540 --> 00:02:20,900 And we come to see over here again we are going to take it. 54 00:02:20,900 --> 00:02:22,340 That's that's at this line. 55 00:02:22,340 --> 00:02:23,690 We take C right. 56 00:02:23,690 --> 00:02:27,050 We are checking whether C is there in our scene hash table. 57 00:02:27,050 --> 00:02:27,950 It's not there. 58 00:02:27,950 --> 00:02:33,020 Again we update max because this part is going to be three and max at currently is just two. 59 00:02:33,050 --> 00:02:34,220 So this becomes three. 60 00:02:34,550 --> 00:02:35,060 All right. 61 00:02:35,060 --> 00:02:36,740 Again we increment I. 62 00:02:36,770 --> 00:02:39,380 So I is going to point to index three. 63 00:02:39,380 --> 00:02:42,020 So again we see over here that the value is b. 64 00:02:42,020 --> 00:02:46,670 And at this point we see that b is already there in our scene hash table. 65 00:02:46,670 --> 00:02:48,410 And again previously we have entered C. 66 00:02:48,410 --> 00:02:49,190 So I forgot that. 67 00:02:49,190 --> 00:02:51,050 So C is having the value two. 68 00:02:51,050 --> 00:02:51,830 The key is c. 69 00:02:51,860 --> 00:02:54,890 Now when we again came to B we see that it's there. 70 00:02:54,890 --> 00:02:57,440 So we see it's there in our hash table. 71 00:02:57,440 --> 00:03:00,860 So we are going to check whether we need to update the start. 72 00:03:00,860 --> 00:03:04,610 Now in this case we have start pointing to zero. 73 00:03:04,610 --> 00:03:12,260 So start at this point is pointing to zero and seen at char is is one and one plus one is two. 74 00:03:12,290 --> 00:03:15,260 So among zero and two the greater value is two. 75 00:03:15,290 --> 00:03:19,160 Therefore we will update the start value right. 76 00:03:19,160 --> 00:03:22,550 So start is now going to point to this one over here which is two. 77 00:03:22,550 --> 00:03:25,130 Because among zero and two two is the greater value. 78 00:03:25,130 --> 00:03:32,300 Again from a logical perspective we are just checking whether start between start and the first in the 79 00:03:32,300 --> 00:03:36,020 previous instance where that particular character occurred, which is greater. 80 00:03:36,020 --> 00:03:36,320 Right. 81 00:03:36,320 --> 00:03:40,820 Whether the the index where that character occurred plus one or start is greater. 82 00:03:40,820 --> 00:03:42,620 So in this case this is greater. 83 00:03:42,620 --> 00:03:44,540 So we change start to here. 84 00:03:44,540 --> 00:03:46,490 And then we are going to check the length. 85 00:03:46,490 --> 00:03:48,830 So in at this point max is three. 86 00:03:48,830 --> 00:03:52,250 But the length between start and b is just two right. 87 00:03:52,250 --> 00:03:54,200 So we are not going to update it again. 88 00:03:54,200 --> 00:03:58,760 We are going to move I so I comes over here we see that D is not there here. 89 00:03:58,760 --> 00:04:00,650 So we are going to check over here. 90 00:04:00,650 --> 00:04:01,370 Max is three. 91 00:04:01,370 --> 00:04:02,930 And the length over here is also three. 92 00:04:02,930 --> 00:04:03,200 Right. 93 00:04:03,200 --> 00:04:04,250 So that happens over here. 94 00:04:04,250 --> 00:04:05,810 So we don't need to update this. 95 00:04:05,810 --> 00:04:07,910 And we are going to make an entry D. 96 00:04:07,910 --> 00:04:09,890 And the entry is going to be four. 97 00:04:10,430 --> 00:04:13,100 Again we move I I comes over here. 98 00:04:13,100 --> 00:04:17,990 Now at this point again we check whether E is there in scene. 99 00:04:17,990 --> 00:04:18,860 It's not there. 100 00:04:18,860 --> 00:04:21,740 Now we are going to see whether we have to update Max. 101 00:04:21,740 --> 00:04:25,010 So over here the length of this substring is four right. 102 00:04:25,010 --> 00:04:26,120 And this is three. 103 00:04:26,120 --> 00:04:28,070 So we have to update this to four. 104 00:04:28,070 --> 00:04:30,650 And we are going to make an entry for E as well. 105 00:04:30,650 --> 00:04:32,660 So e and the value is five. 106 00:04:32,660 --> 00:04:36,590 And again we update I I because I comes to six. 107 00:04:36,590 --> 00:04:39,920 Now we are seeing that it's not there in our scene hash table. 108 00:04:39,920 --> 00:04:43,100 So over here we are going to change the max value to five. 109 00:04:43,100 --> 00:04:45,740 And we are making an entry f and six. 110 00:04:45,740 --> 00:04:51,050 So in this way we are going to find that the length of the maximum substring of this string with unique 111 00:04:51,050 --> 00:04:54,680 characters for this string, which is given to us, is equal to five. 112 00:04:55,010 --> 00:04:56,690 Now that's what is happening. 113 00:04:56,690 --> 00:04:59,030 So this is how our algorithm functions. 114 00:04:59,030 --> 00:05:03,530 Now over here you can notice that we are taking the maximum between start and max. 115 00:05:03,530 --> 00:05:10,760 Let's say for example over here after f for example let's say we have a okay. 116 00:05:10,760 --> 00:05:13,910 So at this point the start is only here. 117 00:05:13,910 --> 00:05:15,980 Start is over here right at index two. 118 00:05:16,010 --> 00:05:17,480 So this is where start is. 119 00:05:17,480 --> 00:05:24,110 Now if we encounter a after uh over here, then there is no point in shifting the start. 120 00:05:24,110 --> 00:05:24,290 Right. 121 00:05:24,290 --> 00:05:29,060 Because logically you can see that we have not started looking from here. 122 00:05:29,060 --> 00:05:30,740 So that is what is happening over here. 123 00:05:30,740 --> 00:05:36,170 So when we check whether we need to change start or not, we are just checking whether which is greater 124 00:05:36,470 --> 00:05:42,680 is start greater, or is the index where that particular character occurred previously plus one. 125 00:05:42,680 --> 00:05:42,920 Right. 126 00:05:42,920 --> 00:05:49,160 So that that's what is computed over here is start greater or is this greater in this case seen at char 127 00:05:49,160 --> 00:05:51,650 will be zero and zero plus one is one. 128 00:05:51,650 --> 00:05:51,890 Right. 129 00:05:51,890 --> 00:05:53,090 If A was there over here. 130 00:05:53,090 --> 00:05:55,670 So among one and two two is greater. 131 00:05:55,670 --> 00:05:57,020 So we don't need to move start. 132 00:05:57,020 --> 00:05:59,570 And in that case we would have just incremented this. 133 00:05:59,570 --> 00:06:02,960 And we could have taken this substring over here which has a length of six. 134 00:06:02,960 --> 00:06:06,020 So this is how our how our algorithm functions. 135 00:06:06,020 --> 00:06:06,650 Now let's. 136 00:06:06,830 --> 00:06:10,100 Take a quick look at the space and time complexity. 137 00:06:10,130 --> 00:06:14,210 Now, when it comes to the time complexity, it is pretty straightforward, right? 138 00:06:14,210 --> 00:06:22,010 We are just traversing the given string once, so the time complexity is O of n if n is the length of 139 00:06:22,010 --> 00:06:22,910 the given string. 140 00:06:22,910 --> 00:06:24,350 So that is pretty straightforward. 141 00:06:24,350 --> 00:06:29,330 So for each value of I we are just doing some constant time operations. 142 00:06:29,330 --> 00:06:31,370 Now what about the space complexity. 143 00:06:31,370 --> 00:06:35,810 Now let's take a look at what all things consume scaling type of space. 144 00:06:35,810 --> 00:06:36,110 Right. 145 00:06:36,110 --> 00:06:39,320 So you can see that it's only this hash table over here. 146 00:06:39,320 --> 00:06:45,980 Now the space complexity therefore will depend on the size or the amount of space our hash table will 147 00:06:45,980 --> 00:06:46,430 take. 148 00:06:46,430 --> 00:06:53,540 Now in this case, we can say that the space complexity is of the order of the minimum between n and 149 00:06:53,540 --> 00:06:59,390 M, where m is the number of unique characters in our string. 150 00:06:59,390 --> 00:07:05,360 So the number of unique characters in our string will depend how big our hash table is going to be. 151 00:07:05,360 --> 00:07:05,660 Right? 152 00:07:05,660 --> 00:07:09,380 Because we are, we are going to make only entries for unique characters. 153 00:07:09,380 --> 00:07:10,010 So. 154 00:07:10,010 --> 00:07:15,500 And the worst case is if all the N characters are unique, in that case, the space complexity will 155 00:07:15,500 --> 00:07:21,500 be O of n, otherwise the space complexity is going to be of the order of the minimum between n and 156 00:07:21,500 --> 00:07:27,140 m, where n is the length of the string which is given to us, and m is the number of unique characters 157 00:07:27,140 --> 00:07:29,210 in the string unique characters. 158 00:07:29,210 --> 00:07:31,460 So this is unique characters in the string.