Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]

to find the longest palindrome substring alright so the interviewer tells you well given a string find the longest substring of the string that's a palindrome what would you ask the interviewer asks you this what would your first questions do the interviewer be alright some great questions there our special characters or commas to be considered or ignored that's a very good question so let's say the interviewer says you don't have to worry about it but that's something that you might have to handle when even you when you're dealing with palindromes you guys know what a palindrome is right it's basically a string which treats the same both ways typically people ignore commas or special characters because it's it's kind of like a part of the language but it doesn't affect the palindrome Ness of a string alright so you have this class of palindromes like Madinah madam right so there is a comma after madam and if you consider the comma you don't have a lot of palindromes which makes a lot of sense in English language so typically ignore special characters but let's say you don't wanna worry about that let's say you're given a string without any special character or solicit interviewer kind of simplifies that it says it's just alphanumeric characters no special characters can a palindrome not exist well that's a possibility yes let's say the panelled room cannot exist let's say you have a string that a palindrome does not exist however I should say that there are different ways of handling this if a string has no sub strings with palindromes that exists well a single character string is a palindrome right two character strings can be palindromes if they repeat but at the very least just take one character and say this is this the parent was the longest palindrome we can find you have a whole lot of those and then there's also a related question what if you have two strings which are palindrome sub strings but they happen to be of the same length well the interviewer can say well written any one of those all right these are great questions all right I hope I hope some of you guys got this this is one of those things where you have like the brute force approach where he can just go like I don't care about time complexity all I want is to find the answer and you just loop and loop and loop and loop you can you can't find the answer that way but what you're looking at is what's the most efficient way to find the answer and that's where that's where the fun is right that's where the complexity of this problem lies so this is not something that you can do that like oh you cannot just do one scan and try and solve it I think you cannot do it in off n square as well mercy will work around this but then this is a fairly intensive operation but then the challenge is to see how fast you can make you can possibly make it but the chance with the constraints that you have all right let's think about this you guys know how to find if a given string is a palindrome or not right it's given a string how do you find out if it's a palindrome or not well that's actually hopefully fairly simple so what you need to do is I mean it is this guy here let's say this is your string ABCDE F II what you need to do is have a pointer at the start have a pointer at the end right compare these two characters if they match move this pointer here of this pointer here compare these two characters if they match both this year so keep doing this have these pointers approach one another until they meet in the middle they hopefully meet in the middle in which case you say okay this whole thing is a palindrome because I've started from both ends I've kind of validated both sides and at each position they will match right this will work but the problem is for something like this you need to know what the start point is and what the end point is if you're saying okay given a string and say check if this is a palindrome you know what the start point you know what the end point is and you can close this way however in this case it's a little different you have to seem any of the substring any of the hundreds of sub possible sub strings for this string happens to be a palindrome what's the brute force way the brute force ways to say okay I'm gonna check for every start I'm gonna check for every end I'm going to do this thing but I'm looking through and then checking each character one by one and then at any point of time I meet in the middle I'm gonna keep track of how many of those characters I add compare which is basically I'm going to get the length of that palindrome substring but I keep track of that somewhere and say okay I found a palindrome of size X starting at position n right and then I'm gonna keep going so I'm gonna do this for every possible start in every possible line okay how do I do that base Vidia nested loop right for I equals 0 to n J equals 0 to n that n is the size of the string that's the can work that can possibly work but then you're basically looping you're having a nested loop which is off n square and for each iteration of that nested loop we are basically comparing the size which is another loop which which which compares the individual characters so this is not efficient is that a better way here's an alternative so but before getting into the the palindrome substring problem let's look back at checking if a given string is a palindrome right I'm gonna give you an alternative way to check if a given string is a palindrome and you will soon see how that applies to checking if the if there are sub strings which are palindromes all right let me show you so let's say instead of starting over here right instead of starting from the beginning in the end let's say this is my string a b c d CB e alright so i want to check if this given string is a palindrome or not instead of starting from here and here right I'm not gonna do that what I'm gonna do instead this start from the middle all right I'm gonna start from the middle and I'm going to expand this way then I'm gonna expand on both sides I'm going to check if this character is equal to this character okay if yes I'm gonna move on check this character is equal to this character if yes I'm gonna move on and then if I have the beginning in the end but then I know that this string is a palindrome it's basically the same thing what I'm doing is essentially the same concept but instead of having just start and end and looping in words I'm gonna start from the middle and loop outwards alright does this work technically this will work but there is a small problem here there was a small problem what if there isn't the middle like the example that I showed you here this one has a middle which is deep this is the guy in the middle right what if I have another string let's say it's like this a b c c b a well this is a palindrome well now can you find can you use this alternative approach this starting from the middle and going outside can you apply this approach to finding if the string is a palindrome or not you technically can but what you need to do is detect that okay this is the middle happens to be two characters now you have to check if the two character middle is the same and then if that's the same go further so you basically need to have this if condition to check okay is the number of characters in my string odd or even if it's odd you have a middle you start from there any expand if it's even you take the middle two characters check if they're equal and then expand right so this is setting aside the problem if we try to solve now setting that aside this is another legitimate way of checking if a given string is a palindrome or not agree that'll work we might ask me well Kaushik then what's the point of doing this because you have to have this additional complexity if you're starting from start and end it's simple right you don't have to worry about whether it's even or odd you can handle that case when you meet in the middle but if you're doing this if you have trying to start from the middle and going outside you have to handle this extra use case why do we need this well here's why we need this this is useful in our particular problem that we're trying to solve the maximum palindrome substring right here's how it helps there's my string now if I were to find out what are all the possible combinations of sub strings that I need to check for palindrome we said if you're going with the start and end approach you have a nested loop right and let me get this straight first of all I have to clarify you have to check each individual substring for a palindrome right there's no other way around there's no magical way of saying okay now I'm gonna do this little trick here so that I don't have to check everything you kind of have to check everything so the question is how we can optimize the everything part all right so let's look at this if you were to look at the start and the end approach right so let's say your URL hürmüz check palindrome and it takes in parameters your string start and then end okay now how do you identify all the sub strings well you're gonna have to do a pulse 0 to length J equals 0 to length maybe you can optimize the starting point of check here a little bit but then the fact remains that you're gonna have to do all these loops and for each loop you need to call check palindrome the string hi Jay alright this is necessary however let's say able to use this other approach this alternative approach which is check palindrome where I'm starting from the middle take the string and then the midpoint now if I were to use this to this method to check if the string is a palindrome one and how many loops do I need I see this I just need one loop because I'm just passing in the midpoint there so what I'm doing is instead of doing a start and a man and then checking of each is a palindrome I'm saying I'm gonna do one pass of the string and see for each character if it happens to be the middle of a possible palindrome alright it's a slight shift in your thinking but imagine how much it saves here you're basically saving an entire loop by having that shift in thinking you're saying I'm gonna do one pass of the string each character I'm gonna expand till I find two mismatched characters and like okay I found some palindrome and you do that for each character and there you go you have a possible solution for the maximum palindrome substrate here's what the code is gonna look like okay so let's say I have a class called solution I don't usually put a class here because but for this particular thing I'm gonna have a couple of member variables and I'll tell you why in a bit but let's say I have a class and this is my strength is my solution method the longest palindrome method which takes in a string and it returns back the longest palindrome all right first thing I'm going to do is get the length of the string and what is the minimum length of the string that I need to have in order to do all this business right boundary check there's the first thing you ask your interviewer do all the boundary checks and say okay what's your behave what's the expected behavior so in this case the boundary check is is a string an empty string very much case you probably do just one order down the string right it's a string of one character in which case what's the longest palindrome we can get out of that it's that single characters string which is the entire string itself right so you basically need to check if your string is of length 0 or 1 then just return the string you don't have to do any of the stuff so that's gonna be mine if block here I'm gonna put enough block there and says if it's less than to just return right now now do the actual stuff what I'm gonna do is I'm gonna loop through the string character by character and I'm gonna check if each individual character is a possible center of a possible palindrome substring and if it is no matter how long the palindrome is I'm gonna keep track of that length I'm gonna keep track of that starting position and then at the end I'm gonna say okay what's the biggest one if I find a bigger one I'm gonna put it to that same variable and then the end whatever that variable holds is the longest common substring right so what I'm gonna do is let's start from zero I'm gonna go until string 1-1 because of zero index start plus plus I'm going to get the possibility of that particular value start being the center of a palindrome so imagine I create this method called expand range alright so this is what this is gonna do like check palindrome was the method that I wrote in the in the notes there but I've called it expanded you call it whatever you want obviously so what I'm gonna do here is pass in two arguments I know there's three there but bear with me pass in two arguments one is a string the other is the midpoint then it returns back the longest palindrome that it can get right however this is not gonna be enough you remember that the midpoint check for a palindrome like starting from the center and expanding up you have another use case to think about which is what if the length of the string is even in which case you don't have one midpoint you have two characters start in an end all right so that's the reason right what I'm gonna do is I'm gonna call the same expand range method with the start and start plus one all right so what expand range does is it doesn't take one midpoint it basically takes two all the time but if the number of characters are odd the range is going to be the same character right so that because there is a midpoint it's going to be a midpoint comma mcfine but then if the number of characters are even it's gonna be those two characters which are which form the midpoint which is what I mean thinking ascending here if I start and start plus 1 they may not be the midpoint but then again we are just trying to see if okay are these two characters possibly a midpoint artha possible palindrome so you have to check for each and every letter each and every alphabet position in that string all right so how am I gonna do this let's say I write this method expand range which takes in a string takes in the beginning it takes in an end right takes in two characters and then it's gonna expand till it finds the largest possible palindrome now I'm gonna create two member variables here because what I want expand range to return is two values I wanted to return the maximum length and I also wanted to return the position where it found the starting of the palindrome right I need to start because I need to do the substring I need to somehow calculate the substring from the string and then return back because that's what the longest palindrome method needs to return it means to actually return the substring itself the biggest palindromes itself so I'm gonna keep track of two men the variables and then the expanded range all its gonna do is gonna write to those member variables and then when they're done I basically do a substring off the result start and then the result start plus the result left alright is this clear so far and of course the reason I do this is because the Java API for substring is basically the start in the end right you need to return the start index and the end index so what I'm doing here is the result start and the result start plus the result in the result length why am I not storing the result end why am i storing the result length I need the results length anyway because we are looking at the maximum palindrome so I need to keep track of the length anyway so I'm keeping track of the length and then I'm doing start plus length all right so as long as expand range does its job right given a string and given a Centerpoint which is two characters it expands and then writes to result start and result length as long as it finds a palindrome which is bigger than this as long as that's expand range job as long as that's doing its job this main method the important method which is the longest palindrome method there's gonna do its job and it's going to return the longest palindrome substring all right so we have delegated that expanding range to the expander inch method hopefully this is clear so far now let's look at the expand range method and see what it does what does it have to do it has to check if the character at the beginning is equal to the character at the end and while it is that while it is true keep going so that's inside of a loop right so vile character at beginning is equal to character at the end I'm gonna do begin minus minus n plus plus but then of course I also have the bounds check so while the gain is greater than zero you don't want to keep doing this beginners equal to 0 or less than 0 and at the same time you don't want to increase end if n has reached string length right so while the begin is greater than or equal to 0 and n is less than the length of the string and these two characters match I'm gonna keep expanding the range right so we can minus minus n plus plus you're checking if that thing that was sent is a middle of a palindrome or at least as big a padded room as you can find once you exit the while loop it means that it's found a palindrome or it just came up right at the beginning whatever it is right it's like the biggest palindrome we can find that that thing is the center now I'm gonna check if the result lent the previous pattern room that I've found if that's smaller than what I've found over here so what if what have I found it's n - begin - one because of zero index right so I'm gonna say n - begin - one that's the length of the palindrome of found is it greater than what I found before if it's greater then I'm gonna save it to the class member member variables when I say result started as begin plus one because I've done a - - now I need to do a plus one to get back to the start of the actual palindrome a result length is n - begin - one because of the zero index of arrays in Java so I'm gonna get that length and then I'm gonna save it to the member variable off this class all right so there's gonna keep happening I'm gonna call expand range twice for each character and then I'm gonna check if that's the center of the palindrome and then we'll find the biggest one that we can find and then the longest palindrome method is returning that as a substring all right so is there a solution again you can of course do the other approach which is basically having start and end and looping through the work for the most part but you are definitely gonna get bonus points if you cannot explain your rationale and say this is why I'm doing this I'm gonna start from the center and move outwards because I get to save on that starting and you have two variables so you need two loops Center you have just one variable so you just need one loop to do that for each each character questions

Channel: Java Brains

Views: 61,004

Rating: 4.7715259 out of 5

Keywords: java brains, java, interview, coding, coding challenge, java interview, java interview questions, interview coding challenge, interview practice, koushik, koushik kothagal, java interview videos, java interview challenge videos, brains, kothagal, kaushik, tutorial, programming, eclipse, beginner, challenge, java programming, java tutorial for beginners, training, java tutorial, java programming tutorial, palindrome, substring, palindrome substring, leetcode, hackerrank

Id: DK5OKKbF6GI

Length: 20min 56sec (1256 seconds)

Published: Sat Mar 07 2020