1
00:00:01,480 --> 00:00:02,590
Welcome back, everyone.

2
00:00:02,830 --> 00:00:06,880
Hopefully everyone got a chance to try their hand at coming up with an optimal solution.

3
00:00:07,300 --> 00:00:12,280
Now, remember, with a lot of these technical interview questions, there are many ways that you can

4
00:00:12,280 --> 00:00:18,010
come up with a solution and they might all have the same space and time complexity, meaning there exists

5
00:00:18,010 --> 00:00:23,770
multiple versions and variations of a optimal solution in this lesson.

6
00:00:23,800 --> 00:00:28,990
I'm going to show you what I would do in order to come up with an optimal solution working off of our

7
00:00:28,990 --> 00:00:34,390
brute force, but also adding some of that logical abstract thinking that we've been talking about this

8
00:00:34,390 --> 00:00:35,260
course thus far.

9
00:00:36,410 --> 00:00:42,020
So when we looked at our brute force solution, we knew that where we needed to optimize was in our

10
00:00:42,020 --> 00:00:43,100
space complexity.

11
00:00:43,550 --> 00:00:51,440
When we had it, we were coming up with a oh of A plus B space complexity because A represented the

12
00:00:51,440 --> 00:00:56,030
size of our string S and B represented the size of our string T.

13
00:00:57,000 --> 00:01:03,570
We would then take these respective strings and run them through some code that would give us back some

14
00:01:03,570 --> 00:01:09,600
kind of scaling data structure, which in this case was an array that would hold the final format of

15
00:01:09,600 --> 00:01:14,840
the string after transformation, transformation being, which characters do we remove if there are

16
00:01:14,850 --> 00:01:16,060
hashes in the string?

17
00:01:16,650 --> 00:01:20,660
So here we know that ABC hashtag D becomes Abdeh.

18
00:01:20,880 --> 00:01:26,010
So we returned Abdeh and similarly with String T, it's the same idea.

19
00:01:26,010 --> 00:01:27,540
It becomes Abde here.

20
00:01:27,570 --> 00:01:35,280
So we had two of these arrays that would both hold whatever the final output of these strings were.

21
00:01:35,880 --> 00:01:42,630
We would then compare the characters inside of these arrays in the exact same position in the arrays

22
00:01:42,630 --> 00:01:44,250
to see if we had a match.

23
00:01:44,880 --> 00:01:46,530
If we did, we would return.

24
00:01:46,530 --> 00:01:49,440
True, if we didn't, we would return false.

25
00:01:50,350 --> 00:01:55,480
But the key here is to realize that the question really is only asking us to return, true or false,

26
00:01:55,930 --> 00:02:03,250
we are choosing to create these data structures, these scaling in memory data structures in order to

27
00:02:03,250 --> 00:02:06,030
help us get to this final answer.

28
00:02:06,550 --> 00:02:11,810
But the question itself does not require us to even create these data structures in the first place.

29
00:02:11,830 --> 00:02:18,760
So that is our first hint that if we know for certain there's no real need for these other than the

30
00:02:18,760 --> 00:02:24,010
fact that our solution depends upon it, our brute force solution in this case, then maybe there is

31
00:02:24,010 --> 00:02:30,190
a way for us to remove this, because if the question required us to return these arrays instead, then

32
00:02:30,190 --> 00:02:31,260
there's no way around it.

33
00:02:31,360 --> 00:02:36,730
You have to create them in your code because the question expects you to create them as part of the

34
00:02:36,730 --> 00:02:37,140
answer.

35
00:02:37,660 --> 00:02:43,900
But our question is simply asking us to return, true or false, depending on the condition, if these

36
00:02:43,900 --> 00:02:47,350
two strings, when typed out, have the same output.

37
00:02:48,350 --> 00:02:54,680
So that might be a way to bring down the memory is to remove these and find some other way to figure

38
00:02:54,680 --> 00:03:00,890
out whether or not it's true or false that these two strings are equal when transformed.

39
00:03:01,520 --> 00:03:03,020
So we'll talk about that next.

40
00:03:03,140 --> 00:03:05,810
But first, let's just get rid of these arrays here.

41
00:03:07,850 --> 00:03:14,210
So knowing what we know now, perhaps what we can think about is some of those hints I gave you, which

42
00:03:14,210 --> 00:03:22,010
is about using the 2.0 structure, if there was a way where we can think about if we had two pointers,

43
00:03:22,040 --> 00:03:29,840
one pointer pointing to an element and s and one points are pointing to an element and T and then just

44
00:03:29,840 --> 00:03:36,590
comparing those letters, because if you were to break this problem down into smaller problems, when

45
00:03:36,590 --> 00:03:42,800
we matched the characters in the arrays, we were matching them character by character, by the position

46
00:03:42,800 --> 00:03:43,530
that they were in.

47
00:03:44,150 --> 00:03:52,820
So similarly, we can move that out and just use the strings that we are given as the actual structure

48
00:03:52,820 --> 00:03:57,020
that we should compare against, because we're really just comparing these strings anyways.

49
00:03:57,260 --> 00:04:05,270
And we can compare whether or not the characters are equal in some position P in this case, maybe P1

50
00:04:05,270 --> 00:04:05,990
and P2.

51
00:04:05,990 --> 00:04:14,030
So I'm more clear here is the character at Espie one the same as the character in T P2.

52
00:04:15,060 --> 00:04:23,850
Now, if we go from left to right, this becomes problematic because if we were to say this character

53
00:04:23,880 --> 00:04:25,890
at P1 here.

54
00:04:28,400 --> 00:04:34,490
And this character at P two, right here in the same place, let's say, right here.

55
00:04:36,530 --> 00:04:43,520
If we were to compare these two, we know that this would not be true just upon evaluation, but then

56
00:04:43,520 --> 00:04:48,950
if we were to look out a little bit and think about the strings themselves, we know that this hash

57
00:04:48,950 --> 00:04:54,010
is going to delete the sea and we know that these two hashes are going to delete these two values.

58
00:04:54,020 --> 00:04:56,900
So this hash is actually going to delete the Z anyways.

59
00:04:57,350 --> 00:05:04,370
So just by comparing these letters, this is not going to work because our backspace deletes backwards

60
00:05:04,370 --> 00:05:10,190
and our points are moving left to right is always going to be one or two steps behind.

61
00:05:10,520 --> 00:05:17,150
In fact, it could be multiple steps behind, depending on how far down multiple hashes might be, because

62
00:05:17,150 --> 00:05:21,220
a row of hashes is going to delete a row of respective characters.

63
00:05:21,620 --> 00:05:26,020
But if we go from left to right, we won't see those hash tags until much later.

64
00:05:26,030 --> 00:05:28,900
So we know that our logic cannot work this way.

65
00:05:29,450 --> 00:05:36,200
Instead, what we can do is knowing that the hash is delete from right to left, then we just move our

66
00:05:36,200 --> 00:05:40,850
pointers and start them from the right instead of starting them from the left.

67
00:05:41,390 --> 00:05:49,520
So here we can initialize P1 at the end of string S and P two at the end of string T, logically speaking

68
00:05:49,520 --> 00:05:55,970
here, because we're starting at the very end, meaning the right side, we know that there are no characters

69
00:05:56,120 --> 00:06:01,220
after this character that we're currently pointed on because it's the last character, which means that

70
00:06:01,220 --> 00:06:05,720
if this character is not a hash, then this character ends up in the final string.

71
00:06:06,200 --> 00:06:10,160
This D is the last character right here in our final string.

72
00:06:10,160 --> 00:06:14,450
Whatever this character is means that this character must be in the final string.

73
00:06:15,110 --> 00:06:21,080
This then means that we don't have to worry about this character being deleted so we can compare this

74
00:06:21,080 --> 00:06:27,620
character, a P one with this character at P two, because both of these characters must be in the final

75
00:06:27,620 --> 00:06:31,650
string format that gets transformed from whatever the string is.

76
00:06:32,360 --> 00:06:37,970
So that means that if the string up one and the string character have to match, then we know we can

77
00:06:37,970 --> 00:06:41,680
move our pointers forward to check the rest of the strings respectively.

78
00:06:42,260 --> 00:06:47,270
If it does not match, then we know that we got a return false because these characters, if they don't

79
00:06:47,270 --> 00:06:50,340
match, means that the character in the final strings don't match.

80
00:06:50,630 --> 00:06:53,840
Which means that we have our answer about this being false.

81
00:06:54,680 --> 00:07:00,380
If they match, what we're going to do is we're just going to move the characters one forward or the

82
00:07:00,380 --> 00:07:01,040
pointers.

83
00:07:01,070 --> 00:07:05,610
So in this case, P two is going to move here and P one is going to move here.

84
00:07:06,440 --> 00:07:13,940
Now, what we do when we encounter a hash tag is we think, OK, there's no point in us comparing these

85
00:07:13,940 --> 00:07:17,880
hashes because what these hashes do is they delete a character.

86
00:07:18,620 --> 00:07:27,770
So what we can then say is that here I want to move my pointer over by two, because what we need to

87
00:07:27,770 --> 00:07:33,800
do is we need to move over to the C and then over again to the B, because the C is going to get deleted,

88
00:07:34,010 --> 00:07:40,100
which means that the logic and rationale here is that I want to remove these two characters, logically

89
00:07:40,100 --> 00:07:42,770
speaking, without actually modifying anything in memory.

90
00:07:42,980 --> 00:07:45,620
So the easiest way to do that is just to move.

91
00:07:45,650 --> 00:07:54,680
This points are over by two, but we're actually not just going to skip P one all the way over to B,

92
00:07:54,980 --> 00:08:03,920
which is two places over, because what we need to see is that if this character here is a hash or if

93
00:08:03,920 --> 00:08:10,310
it's a character, as we see in our string t, so I know that here I just moved it over.

94
00:08:10,310 --> 00:08:12,890
But let's just evaluate why we got to do it step by step.

95
00:08:13,920 --> 00:08:18,930
So here we know that we have two pointing to some hash value.

96
00:08:19,950 --> 00:08:26,310
We can then say that he, too, needs to move left over by two characters, so we're going to move it

97
00:08:26,310 --> 00:08:27,620
over once first.

98
00:08:27,630 --> 00:08:30,300
So PETA is going to move over on consumer step.

99
00:08:30,960 --> 00:08:33,200
This means that PETA moves over by one.

100
00:08:33,210 --> 00:08:36,120
And we have one more step to make from here.

101
00:08:36,120 --> 00:08:42,360
We then evaluate, is this character a hash or is it a letter or some kind of strong character?

102
00:08:42,840 --> 00:08:50,190
In this case, it's another hash, which means that this has to delete another value to the left.

103
00:08:51,090 --> 00:08:59,040
We do not simply delete this character with this first hash, we kind of group these two values together

104
00:08:59,250 --> 00:09:04,410
in a way to see how many characters to the left are there actually to delete.

105
00:09:05,220 --> 00:09:10,260
So because we have another hash, we have another two characters to move over to.

106
00:09:11,010 --> 00:09:15,120
So we have to add two to the number of steps we have yet to make.

107
00:09:15,930 --> 00:09:22,350
And here we then move pizza over again, because there's three steps to be taken, so we move it over

108
00:09:22,350 --> 00:09:25,320
by one and then this three goes down to two.

109
00:09:26,870 --> 00:09:34,760
So then we ask, is the character up to a hash, it's not so we don't need to add any values to the

110
00:09:34,760 --> 00:09:36,040
number of steps we have to take.

111
00:09:36,050 --> 00:09:39,010
We can now just move it over by one and decrement the count.

112
00:09:42,760 --> 00:09:46,890
So now we ask again, is the character up to a hash, it's not.

113
00:09:47,140 --> 00:09:49,480
So once again, we see how many steps we have left.

114
00:09:49,490 --> 00:09:51,850
We have one more, so we decrements it by one.

115
00:09:52,830 --> 00:09:54,390
And then we move to over.

116
00:09:57,310 --> 00:10:02,860
And now we see we have no more steps to take, so we've accounted for all the hashes from when we first

117
00:10:02,860 --> 00:10:11,170
saw our first hash and now P to AMPE one are both in their final places as far as the strings that might

118
00:10:11,170 --> 00:10:12,880
have had any hashes before it.

119
00:10:13,480 --> 00:10:18,790
So we know for sure then that wherever pizza is and wherever P one is is out of character that will

120
00:10:18,790 --> 00:10:21,140
end up in the final string.

121
00:10:21,820 --> 00:10:27,990
So here we see that B and B are in and we can say then OK P one, MP two, do these characters match?

122
00:10:28,300 --> 00:10:28,930
They do.

123
00:10:29,260 --> 00:10:33,130
So then we can now move P1 and P2 over once again.

124
00:10:36,750 --> 00:10:43,020
We check do these final characters match, they do, so we know them for sure, we've explored the full

125
00:10:43,020 --> 00:10:47,190
string on both sides and we can say that conclusively.

126
00:10:47,190 --> 00:10:49,740
We know that this should return true.

127
00:10:50,310 --> 00:10:57,360
The final format of these two strings to match, and that is the technique for using two pointers,

128
00:10:57,390 --> 00:11:05,100
as well as leveraging the strings that were input to us as a way to evaluate whether or not we have

129
00:11:05,100 --> 00:11:07,290
a matching string after the final transformation.

130
00:11:08,280 --> 00:11:15,870
The key to the logic here was realizing that these hashes would be moving a character to the left,

131
00:11:16,320 --> 00:11:22,380
so in order to account for it with pointers, then we have to account for it by starting from the right

132
00:11:22,380 --> 00:11:23,470
of each string.

133
00:11:23,940 --> 00:11:29,160
So that's really the big logical jump that we had to make while using this to point to structure.

134
00:11:29,910 --> 00:11:35,780
And we see now that with this optimal solution, we are actually storing anything in memory.

135
00:11:36,000 --> 00:11:40,470
So chances are we've managed to bring down our actual memory usage.

136
00:11:40,980 --> 00:11:45,040
So with that, I want you to try and code out the solution that we came up with.

137
00:11:45,720 --> 00:11:49,950
I'm going to show you in the next lesson, but I wanted you to try it first.

138
00:11:50,280 --> 00:11:51,330
I'll see you in the next lesson.