1
00:00:00,770 --> 00:00:01,880
Hi everyone.

2
00:00:01,880 --> 00:00:08,150
In this video, let's see how to solve this question in a more optimal manner using a hash table.

3
00:00:08,150 --> 00:00:14,960
Now in the previous solution in the brute force method, the problem why we got a time complexity of

4
00:00:14,960 --> 00:00:21,560
O of n square was for every iteration, for every operation in the first for loop, we again looped

5
00:00:21,560 --> 00:00:22,970
through the array again, right?

6
00:00:22,970 --> 00:00:27,800
So let's try to avoid that using a hash table by storing values into a hash table.

7
00:00:27,800 --> 00:00:29,300
So that's what we are trying.

8
00:00:29,300 --> 00:00:31,070
That's what we are trying to do over here.

9
00:00:31,070 --> 00:00:34,730
Now let's say that the given string is this one over here.

10
00:00:35,300 --> 00:00:39,530
Now let's make an empty hash table at the beginning.

11
00:00:39,530 --> 00:00:48,680
Now what we are going to do is we will first once traverse the given string from this zero to the length.

12
00:00:48,680 --> 00:00:49,100
Right.

13
00:00:49,100 --> 00:00:52,520
So 0123456.

14
00:00:52,520 --> 00:00:53,480
These are the indices.

15
00:00:53,480 --> 00:00:55,280
So we'll go from 0 to 6.

16
00:00:55,280 --> 00:00:59,840
And we will fill the hash table with the characters and the counts.

17
00:00:59,840 --> 00:01:00,260
All right.

18
00:01:00,260 --> 00:01:02,660
So initially the pointer would be over here.

19
00:01:02,660 --> 00:01:06,980
And we will see whether this character A is in the hash table.

20
00:01:06,980 --> 00:01:09,380
Now initially it was empty so it was not there.

21
00:01:09,380 --> 00:01:17,150
So we will enter a into the hash table and we will set the counter or the value to one at this point.

22
00:01:17,150 --> 00:01:17,390
Right.

23
00:01:17,390 --> 00:01:19,100
So this is the key and this is the value.

24
00:01:19,100 --> 00:01:20,660
Now we will set it to one.

25
00:01:20,660 --> 00:01:24,470
Now we will move the pointer from here here to here.

26
00:01:24,470 --> 00:01:25,910
So the pointer is over here.

27
00:01:25,910 --> 00:01:28,490
Now we will check is B in the hash table.

28
00:01:28,490 --> 00:01:29,270
It's not there.

29
00:01:29,270 --> 00:01:32,450
So let's enter B and we set the counter to one.

30
00:01:32,450 --> 00:01:36,080
Now again we move the count the count the pointer over here.

31
00:01:36,080 --> 00:01:37,760
And the pointer is now here.

32
00:01:37,760 --> 00:01:40,550
We will check if capital A is in our hash table.

33
00:01:40,550 --> 00:01:41,660
It's not there.

34
00:01:41,660 --> 00:01:45,860
So we enter it into our hash table and the count is set to one.

35
00:01:45,860 --> 00:01:53,150
Again we will move the pointer to the next character which is again capital A, and because it's already

36
00:01:53,150 --> 00:01:59,270
there in the hash table, we won't insert it again, but rather we will increment this value by one

37
00:01:59,270 --> 00:02:01,070
and we will change 1 to 2.

38
00:02:01,400 --> 00:02:03,770
Now we will again do this with the next character.

39
00:02:03,770 --> 00:02:04,820
One is not there.

40
00:02:04,820 --> 00:02:07,550
So let's insert one and the counter is one.

41
00:02:07,550 --> 00:02:10,130
And again we check for small a.

42
00:02:10,130 --> 00:02:11,000
It's already there.

43
00:02:11,000 --> 00:02:13,250
So we change it from 1 to 2.

44
00:02:13,250 --> 00:02:14,900
And for C it's not there.

45
00:02:14,900 --> 00:02:16,880
So we insert it into our hash table.

46
00:02:16,880 --> 00:02:21,950
So for this we have traversed our string the given string one time.

47
00:02:21,950 --> 00:02:24,260
And we have formed this hash table.

48
00:02:24,260 --> 00:02:24,860
All right.

49
00:02:25,310 --> 00:02:30,770
Now what we will do is we will traverse the given string again one more time.

50
00:02:30,770 --> 00:02:37,700
And we will check which character has a count one as per the hash table that we have made over here.

51
00:02:37,700 --> 00:02:38,210
All right.

52
00:02:38,210 --> 00:02:39,620
So let's look at that.

53
00:02:39,620 --> 00:02:42,620
Now again we have our indices over here.

54
00:02:42,620 --> 00:02:51,680
Now when we are over here we are going to check what is the count for the value a in our hash table.

55
00:02:51,680 --> 00:02:56,840
Now we are definitely sure it's going to be there because we just now traverse the whole string and

56
00:02:56,840 --> 00:02:58,070
made this hash table.

57
00:02:58,070 --> 00:03:00,110
Now we are going to pass the key.

58
00:03:00,140 --> 00:03:03,350
The key is going to be a when we are over here right.

59
00:03:03,350 --> 00:03:04,370
The pointer is over here.

60
00:03:04,370 --> 00:03:05,810
The key is going to be a.

61
00:03:05,810 --> 00:03:08,510
And the value that we get back is two.

62
00:03:08,510 --> 00:03:08,840
Right.

63
00:03:08,840 --> 00:03:10,700
So the value over here is two.

64
00:03:10,730 --> 00:03:11,930
So we move forward.

65
00:03:11,930 --> 00:03:17,210
We are actually looking for a case where when we pass a particular character we should be getting a

66
00:03:17,210 --> 00:03:19,280
value of one from our hash table.

67
00:03:19,280 --> 00:03:25,910
So when we pass the next uh character which is b in this case, when we pass it to the hash table,

68
00:03:25,910 --> 00:03:27,710
we will get back one over here.

69
00:03:27,710 --> 00:03:28,070
Right.

70
00:03:28,070 --> 00:03:29,450
So we are getting one over here.

71
00:03:29,450 --> 00:03:34,370
That means in the given string the character B occurs only one time.

72
00:03:34,370 --> 00:03:35,990
And we have our answer.

73
00:03:35,990 --> 00:03:38,420
And we just need to return the index one.

74
00:03:38,660 --> 00:03:39,860
So that's the answer.

75
00:03:39,860 --> 00:03:44,270
And we were able to do it in a much better time complexity.

76
00:03:44,270 --> 00:03:45,560
Let's look at it now.

77
00:03:45,680 --> 00:03:48,290
Now what's the time complexity over here.

78
00:03:48,800 --> 00:03:52,850
We can see that we had to do N operations to make this hash table.

79
00:03:52,850 --> 00:03:56,270
And again n operations to traverse the string.

80
00:03:56,270 --> 00:03:56,660
Right.

81
00:03:56,660 --> 00:03:59,960
So the time complexity net is O of n.

82
00:03:59,960 --> 00:04:00,650
Why is that.

83
00:04:00,650 --> 00:04:07,610
So again that's n operations over here to make the hash table and n operations to traverse the string

84
00:04:07,910 --> 00:04:08,690
the second time.

85
00:04:08,690 --> 00:04:08,990
Right.

86
00:04:08,990 --> 00:04:11,840
So that's n plus n which is equal to two n.

87
00:04:11,840 --> 00:04:14,420
But again we can just avoid a constant.

88
00:04:14,420 --> 00:04:18,350
Therefore the time complexity of this solution is just O of n.

89
00:04:18,350 --> 00:04:24,260
So this is much better than the time complexity of the brute force solution which was O of n square.

90
00:04:24,290 --> 00:04:26,960
Now what about the space complexity here?

91
00:04:26,960 --> 00:04:28,010
It is a bit tricky.

92
00:04:28,040 --> 00:04:33,320
Now the space complexity of this solution is also o of one.

93
00:04:33,320 --> 00:04:33,920
Now you.

94
00:04:33,920 --> 00:04:36,800
When you say this to the interviewer, you need to clarify why.

95
00:04:36,800 --> 00:04:44,900
Now in the question, it's given that the input string is only made up of lowercase English letters,

96
00:04:45,470 --> 00:04:50,780
uppercase uppercase English letters, and integers 0 to 9.

97
00:04:50,780 --> 00:04:51,290
All right.

98
00:04:51,290 --> 00:04:59,060
So in the case of lowercase, a maximum of 26 characters is possible in the case of uppercase English

99
00:04:59,060 --> 00:04:59,990
letters max.

100
00:05:00,400 --> 00:05:06,670
Of 26 characters is possible, and in the case of integers 0 to 9, that's a maximum of ten characters,

101
00:05:06,670 --> 00:05:07,060
right?

102
00:05:07,060 --> 00:05:12,850
So the maximum possible number of characters, unique characters, which can be there in the string

103
00:05:12,850 --> 00:05:17,890
which we are given is 26 plus 26 plus ten, which is equal to 62.

104
00:05:17,920 --> 00:05:24,760
Now, if we say that the space complexity is O of 62, that's the same as O of one, because this is

105
00:05:24,760 --> 00:05:26,290
just a constant, right?

106
00:05:26,290 --> 00:05:33,100
So that's why we can say that the space complexity of this algorithm is O of one, which is constant

107
00:05:33,100 --> 00:05:33,640
space.