Longest palindromic substring is a quite easy problem- -especially if you have some experience in competitive programming, We are given a string S with lengths up to 1000 and we should find the longest palindromic substring. A substring, which is a palindrome, So it reads the same backwards. First let’s think how to check if a string is a palindrome. We can reverse a string which is quite easy in many programming languages and then compare the two strings, The initial one, given one that we want to check and the reversed one, if they are the same, We have a palindrome and for this one we would (when) reversed have e c c e and here we have equality, This means that “ecce” is a palindrome. This was one way, the other is to compare characters one by one Indices are usually from 0 to n-1 and we need to compare 0 with n-1, then 1 with n-1-1, generally i with n-1-i. We can iterate with i from 0 to n/2 or just from 0 to n-1 then we will repeat some comparisions, but it’s ok, the complexity of both these methods is just O(N) and either we iterate with for loop over n elements and every time we do one comparison or we reverse the string, This is O(N) and and also comparing two strings is O(N) where n is length of a string. Quick look at pseudocode for both these methods, either we S with reverse of S or we iterate with i and check if two characters are different. The slowest solution for this problem will be to check for every substring, if it’s a palindrome and if yes, save it as a possible answer. I will remember length of a string and now for every left bound, let’s call it L from 0 to n-1 and for every right bound From L inclusive because maybe it’s just one character, In particular one character, Here, I meant till n-1 inclusive One character substring is a palindrome R ++, if this is a palindrome from L to R s.substr(L,R-L+1) this thing that we want to take substring, if this is palindrome, is_palindrome of that Then we consider that as an answer. If we were just looking for the length, I would say answer is max(answer,R-L+1) But we also need a string, We need to save a string so I will say int best_length best_length is 0 string best_s is just empty and here if R-L+1 is greater than best_len Then best_len update. And this is s.substr… so because I reuse it, let’s save it. This is subs is s.substr this… Also, why not save the length Now the code will be a bit nicer even though the number of lines increased, if this is a palindrome and length is bigger, I can just put it here and len is greater than best_len then I update best_len is len and best_s is subs. At the end, return best_s. I can run this just to check if it works for the sample test But the complexity is O(N) for this part, iterate over left end, right end, this is already in O(N*N) and every time inside, I use is_palindrome which is linear as well So it’s O(N^3). it worked for the sample test, I can submit but I expect time limit exceeded or maybe Accepted with very big running time and this shouldn’t be, this is for sure not expected in this problem I got time limit exceeded. It will be slightly faster if I put comparison of length first because C++ has lazy if-conditions so if it is that the first one is not true, that we will not increase the length, then it will not even run the second check, if you write something like if(condition1 && condition2) in c++ and condition 1 is false then compiler already understands that this cannot be true in total, So it will not check it the second condition This should be slightly faster But doesn’t change the complexity. From time to time something like this will change the complexity in some problems because you can prove that only this second thing will be run some number of times But here it is not the case One improvement to this slow solution would be to implement this is_palindromic in the other way that I expect to be slightly faster Because here we do something with memory, We create a new string, We reverse it, It would be faster to just iterate with for loop over characters and also break when we have a mismatch, if you also here add const string and add ampersand, so we pass by reference, then usually for loop will not be linear It will be faster because if the first character is already a mismatch then we don’t need to compare. Though, maybe still a string will be just consisting of letters a and everything will be a palindrome because every substring will be just a a a … This will be linear then, But maybe thanks to also this condition, it will be faster because we will increase the length of answer by one only linear number of times that maybe if you use enough fixes, enough improvements, maybe it will be quadratic instead of cubic, but proof would be quite hard. In your coding interview, you want to be able to prove your complexity. One more thing to notice is that this operation is also linear, when we overwrite the substring that we would print at the end It doesn’t matter here because anyway a moment ago we use is_palindrome which is linear So it’s O(N) + O(N) , so O(2*N) But if you wanted to improve such a small part, in maybe some other problem, it would be an issue, You could here save Instead of doing that you could save best_start is L, best_end is R and at the end here return substring s.substr(best_start,best_end). You need to save the the length but it is possible to replace this linear part with something constant and only at the end retrieve the substring that you should return This was N^3 and we will improve it now, If you want to think about it yourself pause the video now and if not We’ll first think about O(N^2*log N) and then the intended version that is O(N^2). Also O(N) is possible with manacher’s algorithm. It’s called manacher, you can read about it, but it’s much harder and we’ll focus just on N^2. This log(N) can come from many things but in particular it might be some sorting or here, binary search. If you should find the longest something you can binary search over this length One idea is to do the following- if you have L, the start of your substring then maybe you can binary search, R. So starting from this position how far to the right you can go to still have a palindrome but this is not correct and an example of that is, let’s say that starting from some position we have say ABBA and then maybe something more But when you binary search and you check for example, if this substring of length three is a palindrome The answer will be no, It is not a palindrome and binary search would then try to find a shorter palindrome. This is why it’s not correct to binary search over the right end for fixed left end. Binary search works if and only if say for some value (something) is good means that also every bigger value is good, then you can binary search. Because every prefix will give you one outcome and every suffix will give you the other outcome But what is correct is to do a general binary search over the answer and to here Say minimum or something like that That’s called low=1, high=N and now binary search over the answer We would need to say though when there is palindrome of some length- -there will be also a shorter palindrome, if you have some very long string and in particular there is abttba such a substring that is a palindrome Then it’s of length 6 But in particular it has inside, a substring, palindromic substring of length 4 This shows that if there is a palindrome of length 6 then if you just remove first and last character you also have 4, and also have 2 and so on. This is a proof why if there is correct length X there will be also X-2, this is it not enough for binary search to work because maybe there are those lengths that are correct, There is a substring of this length, but not of the other parity, so a correct complicated solution in N^2*log(N) is to check every parity so it’s something like for parity in 0 & 1 Now binary search the best length with this parity low is 1, high is N and now we only need this parity, So I will say if low%2 is different than parity than low++ If high%2 not equal to parity then high–. what I did is I had 1 and n and I decreased it, this interval for search only to proper parity, if parity is 0- It should mean that I search only even lengths So instead of this boundary from 1 to 9 where I binary search, it would be only from 2 to 8. Ok, and now while(lowhigh Then break already, I didn’t find anything And now if(good(mid)) So there is a substring of this length then consider this as an answer, best_len is max(best_len,mid) mid is that possible answer, length of a palindrome, But what is function good? It should check if there is a palindromic substring of this length, mid and I can implement this function good of length x, also I need to pass string S. It would be for every L, for every start If is_palindrome of s.susbtr(L,x) so starting at L with length x then return true because there is a palindrome, This should returns true if there is a palindrome of length x and the complexity of this is quadratic O(N) times O(N) for checking the palindrome But thanks to binary search we run this function good only logarithmic number of times and it would be here if(good(mid)) then update the best_len, also update the best_s and low is mid+1 but also fix the parity, but because mid has good parity, then I would do this, low is mid+2 else high is mid- 2 Yes, so it’s something like that. I will now remove this and quickly fix any compilation errors like, I will in particular fix this. I need to change function good so it would return the starting position Here say return L, and otherwise return -1 Because I need that to retrieve the answer and if good is not tmp is good(mid) if tmp is not -1 So I found a palindromic substring of this length mid then here best_s is s.susbtr(tmp,mid). I still expect some compilation errors Maybe other issues,I didn’t care that much about the correctness here and it’s missing In good I need to pass S. Oh, I had a mistake here, I check with L from 0 to n Actually, I want this to be true, L+X=0 and mid+x=0 and mid+x


Leave a Reply

Your email address will not be published. Required fields are marked *