1 00:00:00,840 --> 00:00:01,830 Hi everyone. 2 00:00:01,830 --> 00:00:07,710 In this video let's try to code together the optimal solution which we discussed in the previous video. 3 00:00:07,740 --> 00:00:15,450 Now to start with, let's create a function and let's call it find non-repeating character. 4 00:00:18,790 --> 00:00:21,370 And this function takes in a string. 5 00:00:22,940 --> 00:00:23,450 All right. 6 00:00:23,450 --> 00:00:29,570 Now what we are going to do is we are going to create a hash table, and we will traverse the string 7 00:00:29,570 --> 00:00:37,520 once and we will insert into the hash table each character and the count, or how many times that particular 8 00:00:37,520 --> 00:00:39,890 character is, is occurring in the string. 9 00:00:39,890 --> 00:00:40,280 Right. 10 00:00:40,280 --> 00:00:45,620 And afterwards we will traverse the string again and find the first character which is coming in the 11 00:00:45,620 --> 00:00:49,760 string, which has only a count of one in the hash table which we created. 12 00:00:49,760 --> 00:00:52,280 So let's start by creating a hash table. 13 00:00:52,280 --> 00:00:54,410 Let me call it hash table itself. 14 00:00:55,680 --> 00:00:57,180 So this is a hash table. 15 00:00:57,180 --> 00:00:59,100 It's an empty hash table at this point. 16 00:00:59,130 --> 00:01:06,240 Now let's traverse the given string and let's fill into this hash table the characters and the count, 17 00:01:06,240 --> 00:01:10,620 or how many times each particular character is occurring in this input string. 18 00:01:10,620 --> 00:01:18,180 So for this let's say let I is equal to zero I less than string dot length. 19 00:01:19,060 --> 00:01:20,620 I plus, plus. 20 00:01:22,240 --> 00:01:25,150 Now we are going to check if string. 21 00:01:25,150 --> 00:01:31,210 If the character at the ith index in the string is there in the hash table or not. 22 00:01:31,210 --> 00:01:33,640 So if string I. 23 00:01:37,580 --> 00:01:39,500 In hash table. 24 00:01:39,500 --> 00:01:43,940 So if it's there, what we'll do is we'll increment the value. 25 00:01:44,270 --> 00:01:46,490 So over here string I is the key. 26 00:01:46,490 --> 00:01:48,860 So we are checking the hash table. 27 00:01:48,860 --> 00:01:50,870 If this key is there in the hash table. 28 00:01:50,870 --> 00:01:53,360 If it's there we will increment the count by one. 29 00:01:53,360 --> 00:01:54,980 So hash table. 30 00:01:57,730 --> 00:01:58,600 String I. 31 00:02:00,360 --> 00:02:01,320 Plus plus. 32 00:02:01,320 --> 00:02:03,390 So we are incrementing the count by one. 33 00:02:03,390 --> 00:02:09,870 Now, if it is not there, what we do is we will insert the key value pair into the hash table, and 34 00:02:09,870 --> 00:02:14,100 the key will be the character, and the value will be one because it's not there. 35 00:02:14,100 --> 00:02:15,990 So it's being inserted for the first time. 36 00:02:15,990 --> 00:02:18,120 So we say hash table. 37 00:02:19,850 --> 00:02:21,260 At a string I. 38 00:02:24,360 --> 00:02:25,350 That's the key. 39 00:02:25,350 --> 00:02:28,080 And we are giving the value one. 40 00:02:28,380 --> 00:02:28,860 All right. 41 00:02:28,860 --> 00:02:33,540 So at the end of this for loop we will have created the hash table. 42 00:02:33,540 --> 00:02:42,690 And in the hash table let's say for an for an example let's take a uh the string as a b b d. 43 00:02:42,930 --> 00:02:48,690 Now at the end of this for loop, which we just now have written, the hash table will have the values 44 00:02:48,690 --> 00:02:54,480 a and the count is one for b, the count is two, and for d the count is one. 45 00:02:54,480 --> 00:02:58,230 So this is what will be there in the hash table at the end of this for loop. 46 00:02:58,230 --> 00:03:02,520 Now what we need to do is we will traverse the given string again. 47 00:03:02,520 --> 00:03:08,010 So for let I is equal to zero I less than string. 48 00:03:08,830 --> 00:03:10,120 Dot length. 49 00:03:11,020 --> 00:03:12,490 I plus plus. 50 00:03:12,490 --> 00:03:20,800 And we are going to check whether the count for the character string at the string I the character at 51 00:03:20,800 --> 00:03:22,690 the ith index in the given string. 52 00:03:22,690 --> 00:03:28,510 If the count for that string for that character in the hash table which we have made is one or not. 53 00:03:28,510 --> 00:03:29,920 So that's what we're going to check. 54 00:03:29,920 --> 00:03:32,800 So if hash table. 55 00:03:34,580 --> 00:03:35,540 String I. 56 00:03:38,000 --> 00:03:39,170 Equal to one. 57 00:03:39,170 --> 00:03:40,400 So that's what you are checking. 58 00:03:40,400 --> 00:03:44,810 Now, if this is true, then we have found the first non-repeating character. 59 00:03:44,810 --> 00:03:48,380 And we just need to return the index where this is happening. 60 00:03:48,380 --> 00:03:50,330 So let me change this a bit. 61 00:03:50,330 --> 00:03:52,790 So let's say I write one more a over here. 62 00:03:52,790 --> 00:03:55,940 So that over here the count would be two. 63 00:03:55,970 --> 00:03:59,300 So what will happen in this case is first I will be zero. 64 00:03:59,300 --> 00:04:03,980 And that's a so string of I will be a and we will check in the hash table. 65 00:04:03,980 --> 00:04:04,910 So the count is two. 66 00:04:04,910 --> 00:04:06,800 So this will not return. 67 00:04:06,800 --> 00:04:07,760 It will it will be false. 68 00:04:07,760 --> 00:04:10,580 It will not go inside again I will be incremented. 69 00:04:10,580 --> 00:04:12,080 We'll get to be right. 70 00:04:12,080 --> 00:04:17,000 And the value for b is two again I is incremented again we get to be. 71 00:04:17,000 --> 00:04:18,380 The value for b is two. 72 00:04:18,380 --> 00:04:22,370 Again the I the value of I is incremented and we get two d. 73 00:04:22,400 --> 00:04:25,280 Now in this case d will have the count one. 74 00:04:25,280 --> 00:04:29,240 So hash table at d is will be equal to one. 75 00:04:29,240 --> 00:04:31,760 Therefore we will return the index of d. 76 00:04:31,760 --> 00:04:33,830 In this case that's 0123. 77 00:04:33,830 --> 00:04:35,450 So that's what's happening over here. 78 00:04:35,450 --> 00:04:40,580 Now if this has happened and we were not able to return anything. 79 00:04:40,580 --> 00:04:46,760 So there is no non-repeating character in this case we just need to return null, which is the clarification 80 00:04:46,760 --> 00:04:48,350 that we got from the interviewer. 81 00:04:48,350 --> 00:04:48,890 All right. 82 00:04:48,890 --> 00:04:51,920 So let's test our code now for this. 83 00:04:51,920 --> 00:04:53,120 Let's write a test case. 84 00:04:53,120 --> 00:04:56,210 Let's say a is equal to. 85 00:04:57,060 --> 00:05:03,390 Let's take it as one A, two a and one again. 86 00:05:03,390 --> 00:05:06,600 So in this case two is the first non-repeating character. 87 00:05:06,600 --> 00:05:10,440 Now let's pass it and console.log this. 88 00:05:10,440 --> 00:05:16,080 So let's pass A to our function find non-repeating character and we pass A to it. 89 00:05:16,080 --> 00:05:16,530 All right. 90 00:05:16,530 --> 00:05:18,570 So let's now see what's happening. 91 00:05:18,570 --> 00:05:20,610 So we are going to run it now. 92 00:05:21,060 --> 00:05:26,250 And we get the value 2012 which is the correct index of two. 93 00:05:26,280 --> 00:05:29,910 Now what if I add another two over here and run it again. 94 00:05:30,180 --> 00:05:31,200 So I get null. 95 00:05:31,200 --> 00:05:32,610 So we have reached over here. 96 00:05:32,610 --> 00:05:34,710 So there is no non-repeating character. 97 00:05:34,710 --> 00:05:37,890 What if I add let's say capital F to this. 98 00:05:37,890 --> 00:05:39,930 And again I run it I get six. 99 00:05:39,930 --> 00:05:42,420 So 0123456. 100 00:05:42,420 --> 00:05:44,190 That's the index of capital F. 101 00:05:44,190 --> 00:05:47,610 What if I add another capital F. 102 00:05:47,610 --> 00:05:57,300 And let's say I add a small G and a capital G and I run it, I get eight which is the index where small 103 00:05:57,300 --> 00:05:58,020 g occurs. 104 00:05:58,020 --> 00:06:03,990 And as we have clarified from from the interviewer, we are not considering small G and capital G to 105 00:06:03,990 --> 00:06:04,800 be the same character. 106 00:06:04,800 --> 00:06:07,350 So yes, our algorithm is working fine. 107 00:06:07,350 --> 00:06:15,360 Now let's take another test case and walk through this once more and take a relook at the code that 108 00:06:15,360 --> 00:06:16,200 we have written.