What's up, guys, in here?
And in this video, we are going to solve yet another recording interview question, which is called
Longest Palindromic Substring.
And it is asked a lot of big companies like Google, Facebook and Amazon Killock to become a go when
you get finished.
I got a look at a.
And let's read the statement.
Longest palindromic substring given a string s.
Find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000.
Right.
So a substring is a sequence of consecutive characters'.
Now, for example, number one.
B, a, B, a, D..
The answer is B, a, B of length free.
Right.
And a possible valid answer is a, b, a..
They are palindromes.
Now, for example, number two, cbb d..
The answer is B B, right.
If the string was C, BBC C, CBC is a palindrome.
UNflagged four.
So that would have been the answer.
All right, guys, we all know what is a substring.
We all know what is a palindrome.
If we still have any doubts, takes some time and clarified those and post the video right now and think
about the first brute force approach, which would be Bigo of N Cube.
Go for it.
And I hope you all got it, guys, because it's actually super intuitive.
If we did it, that's cool.
What is a substring substring.
Is defined by two pointers.
The left position and the right position.
So a brute force approach would be to try out each possible substring.
So make a for loop for the left position.
Right.
A formal from position on the position and make the second for loop for the right position.
Right.
Starting at left position all the way to the end position.
Now we have our left.
We have our right.
We have to check if this substring is a palindrome.
And how can we do that?
We can do it linearly.
So let's see right here.
If you have the left and the right.
All right.
In order to check this, we can have another two pointers, an I, which is initially equal to the left
pointer and another J, which is initially equal to the right point.
And we can make a while loop.
So while I is less than J and S of eye is equal to S of J.
What we can do here is actually increase our eye and decrease our J.
And when this way loop successfully finishes execution, we should check if AI is greater or equal then
J.
And if it is, we can return.
True.
Because this substring is a palindrome.
If not, we will just return false.
Right.
So this is how we check in linear time.
If that substring is a palindrome.
So our time complexity for this brute force approach is going to be bego of and cube M squared.
Possible substring linear time to check those.
It is N Cube not because the maximum length of S is 1000.
Obviously they want to have a big go off and square time complexity.
And for this we have to reduce something.
So let's think about this reducing.
Right.
We have an squared possible solution.
So N squared solutions.
Right.
Crossed Bego of N.
Time for checking those.
Right.
And let's think again of our brute force approach.
Right.
So we basically have M squared possible solutions.
And for each of those it takes Bigo of M to try.
So we have either to reduce the number of possible solutions, either to reduce the time in which we
check those.
The number of possible solutions is still going to be big off and squared.
But we can be smarter about the checking.
And how will we do that?
Let's think about the brute force approach.
Right.
For each new possible solution, we basically go again and check that solution from scratch.
We shouldn't do that.
So can we use the fact that we have already checked some possible solutions and not the answer for those
in order to compute the answer for this possible solution?
And we can add, does it sound familiar?
It is dynamic programming, guys.
So step one is now completed, guys.
As you can remember, step two when solving a dynamic programming problem is to find the recurrence
relation.
And you will put this video right now and think about how to compute DEPI of I n g using other debates.
I really hope you guys if not, there's not a problem.
Let's think a little bit about this substrate.
How does he look like?
Well, as of I.
S of eyeballs on dot dot dot s of G Manus Island s of G.
So the first requirement for these substring to be a palindrome is that the fourth and the last element
are equal.
Then if those two are equal, why it remains to hold.
Is that the substring from position eight plus one all the way to position GMAT as one is a palindrome
too.
So DEPI of I NJ you just going to be equal to as of eye is equal to SLG and DEPI of eye plus one and
Giovanna's for.
First thing first, we are going to take the size of the string into a variable and so it is equal to
as that size.
Then we are going to define our DP two dimensional array.
So vector a vector of bool DP.
And we will have ambrosial and concentrate.
So all of these vectors of ball of again size and and let's say they are initially all false, then
we will need to nested for loops.
So the first one is going to be with the eye from M minus one all the way to zero minus smilers or minus
minus.
And the second one for the J.
So position.
I j less than.
And J.
Plus plus.
And now we have to take care of the court case.
So the first corner case is if I equals J.
That means dpf i n g is going to be true.
Obviously that if not, let's say if J equals eight plus one.
This is a corner case to DEPI of I and J is going to be equal to obviously S of I equals as of J.
Now as we are going to use the Riccardo's relation, which is people of J.
Is equal to as of eye equal says of G and DEPI of Eye plus one and G minus one.
Right.
And that's basically it.
And after concluding debut of I and J.
We should see if this offering is a valid one and wait up.
Maybe.
Yes.
All right.
So if deeply of I n g show.
So it's a palindrome.
And we shall object to this whole thing has allowed greater than the maximum three.
So we know very well that makes up, which is should zero.
And so on.
That would be our point.
Right.
For the answer or something.
So I said.
S right.
So if this is a very good subject, n g minus.
Last one is greater than backslap.
That means that we will have a U.
S.
So Max and Jim Ryan say so the answer is going to be equal I.
And the answer is going to be equal to J.
Which is perfect.
Now after finishing his true nested for loops, we shall return our answer and for doing that in C++.
There is the subset, the roof function.
And let's use that.
So return as NSF as the R of.
We shall write.
The first document is the start position.
So Ancef.
And the second one is the left.
So maxilla.
This is perfect.
And now obviously, as always, a corner cases when the string is empty.
So it's an equal to zero.
We shall just return to this tree and it should work, guys.
Matthew, the summary bottom.
Fingers crossed.
I have accepted already.
So let's see.
All right.
All right, guys.
So this was the longest palindromic substring coding interview question again, asked very often until
companies like Amazon, Google and Facebook and make sure to support the channel.
Hit that like button, smash the subscribe button and make sure you hit the notification bell button
to get online videos and notifications for me.
And until the next one by.