1 00:00:00,600 --> 00:00:05,580 Hi everyone, we have successfully coded the optimal solution for this question. 2 00:00:05,580 --> 00:00:11,490 Now let's take a sample input and walk through the code and see what's happening. 3 00:00:11,490 --> 00:00:14,820 Let's say this is the given string and we are passing it to the function. 4 00:00:14,820 --> 00:00:16,710 Find non-repeating character. 5 00:00:16,710 --> 00:00:21,150 Now the indices of the given string are 01234567. 6 00:00:21,150 --> 00:00:29,040 Right now in this part of the code where we have the first for loop, what we are doing is we are building 7 00:00:29,040 --> 00:00:29,970 the hash table. 8 00:00:29,970 --> 00:00:30,390 Right. 9 00:00:30,390 --> 00:00:32,160 So how is that happening? 10 00:00:32,160 --> 00:00:33,990 Initially I is equal to zero. 11 00:00:34,470 --> 00:00:39,540 When I is equal to zero, we take the character in the given string at the ith index. 12 00:00:39,540 --> 00:00:43,380 That's string of I, and we are checking whether it's there in the hash table. 13 00:00:43,380 --> 00:00:46,020 Initially the hash table is empty, so it's not there. 14 00:00:46,020 --> 00:00:51,390 So if it's not there it goes to the else and it gets inserted into the hash table. 15 00:00:51,390 --> 00:00:57,750 So we are inserting the key as a because this is a and the count as one. 16 00:00:57,750 --> 00:00:58,170 Right. 17 00:00:58,170 --> 00:01:00,780 So we are just inserting the count as one. 18 00:01:00,780 --> 00:01:04,470 Then I becomes one right I becomes one. 19 00:01:04,470 --> 00:01:08,940 And the character over here in the string at index one is B. 20 00:01:08,940 --> 00:01:09,690 It's not. 21 00:01:09,690 --> 00:01:11,760 We are checking whether it's there in the hash table. 22 00:01:11,760 --> 00:01:12,510 It's not there. 23 00:01:12,510 --> 00:01:14,760 So we are inserting it B one. 24 00:01:14,760 --> 00:01:18,480 And again we are coming to a when I is equal to two. 25 00:01:18,480 --> 00:01:23,760 Now at this point a character A is already there in the hash table. 26 00:01:23,760 --> 00:01:26,370 Therefore we are just incrementing the value. 27 00:01:26,400 --> 00:01:30,300 We are passing string I, which is a as the key to the hash table. 28 00:01:30,300 --> 00:01:33,810 We'll get back one and we are incrementing that one by one. 29 00:01:33,810 --> 00:01:39,090 So this one changes to two in this manner by traversing the string. 30 00:01:39,090 --> 00:01:41,790 Once we are building this hash table over here. 31 00:01:41,790 --> 00:01:45,990 So that's what's happening in this part of the code right now in this for loop. 32 00:01:45,990 --> 00:01:49,830 What we are doing is we are again traversing the string. 33 00:01:50,280 --> 00:01:52,440 Initially I is equal to zero right. 34 00:01:52,440 --> 00:01:54,990 So string of I is a. 35 00:01:55,020 --> 00:02:00,180 We are passing the key A to the hash table and we are getting back the value two. 36 00:02:00,210 --> 00:02:04,650 So when I is equal to zero this part over here is equal to two. 37 00:02:04,650 --> 00:02:05,970 And two is not equal to one. 38 00:02:05,970 --> 00:02:08,610 So we are again incrementing I by one. 39 00:02:08,610 --> 00:02:12,660 So when I is equal to one we are getting this two back again. 40 00:02:12,660 --> 00:02:18,120 It's two when I is equal to two when I is equal to two, we are again passing a right. 41 00:02:18,120 --> 00:02:21,000 So when we pass a we get back this two again. 42 00:02:21,000 --> 00:02:23,070 So again we have we don't have one. 43 00:02:23,070 --> 00:02:24,960 So again I is incremented. 44 00:02:24,960 --> 00:02:27,060 Now let me make some space over here. 45 00:02:28,680 --> 00:02:32,700 At this point, when I is equal to three, we are passing capital R. 46 00:02:32,730 --> 00:02:37,260 Right now in our hash table for capital R the value is one right. 47 00:02:37,260 --> 00:02:42,570 So when I is equal to three this part over here is equal to one. 48 00:02:42,570 --> 00:02:43,650 One is equal to one. 49 00:02:43,650 --> 00:02:45,750 So we enter over here right. 50 00:02:45,750 --> 00:02:47,250 We are able to enter over here. 51 00:02:47,250 --> 00:02:50,100 And over here it says return I. 52 00:02:50,130 --> 00:02:51,930 So we will return three. 53 00:02:51,930 --> 00:02:54,000 And that ends this function. 54 00:02:54,000 --> 00:02:57,660 And we get the index of the first non-repeating character. 55 00:02:57,660 --> 00:02:59,850 Now let me make some space over here. 56 00:02:59,880 --> 00:03:03,810 Now let's quickly look at the time and space complexity of this solution. 57 00:03:03,810 --> 00:03:07,740 The time complexity of this solution is O of n right. 58 00:03:07,740 --> 00:03:14,460 We have n operations to make the hash table, and we do n operations over here when we traverse the 59 00:03:14,460 --> 00:03:15,390 string once. 60 00:03:15,390 --> 00:03:17,460 But this is not nested right. 61 00:03:17,460 --> 00:03:19,470 You can notice that this is not nested. 62 00:03:19,470 --> 00:03:22,650 So the total operations in this case will be n plus n. 63 00:03:22,650 --> 00:03:26,460 So we can say that the time complexity is O of two n. 64 00:03:26,460 --> 00:03:31,890 And because two is a constant, we can just remove it and we get the time complexity as O of n. 65 00:03:31,890 --> 00:03:35,250 Now the space complexity is O of one, right? 66 00:03:35,250 --> 00:03:36,180 Why is that so? 67 00:03:36,180 --> 00:03:42,930 Because in the question it's given that the string which will be given to us will only consist of small 68 00:03:42,930 --> 00:03:46,620 letters, uppercase letters, and integers 0 to 9. 69 00:03:46,620 --> 00:03:51,570 Now, in the case of small letters in the English alphabet, there are 26 possibilities. 70 00:03:51,570 --> 00:03:57,300 For uppercase letters, there are 26 possibilities, and for integers 0 to 9, ten possibilities. 71 00:03:57,300 --> 00:04:02,250 So the total possibilities is just 26 plus 26 plus ten. 72 00:04:02,250 --> 00:04:02,670 Right? 73 00:04:02,670 --> 00:04:05,880 So that's actually only 62 possibilities. 74 00:04:05,880 --> 00:04:12,840 So we can say that the space complexity is O of 62, which is the same as saying that the space complexity 75 00:04:12,840 --> 00:04:14,790 is O of one, which is constant space. 76 00:04:14,790 --> 00:04:17,190 Because this is just a constant right now. 77 00:04:17,190 --> 00:04:23,160 If this was not given, if it was not mentioned that the string would consist only of these characters, 78 00:04:23,160 --> 00:04:26,160 then the space complexity would have been O of n.