Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]
Vložit
- čas přidán 6. 03. 2020
- Have you seen the new Java Brains? Check out www.javabrains.io now for awesome courses and content!
Interview Question: Find the longest palindrome substring from the given string
Leetcode link: leetcode.com/problems/longest...
Solution Gist: gist.github.com/koushikkothag...
Difficulty level: Medium
Language: Java
Welcome to the Java Brains Java Interview challenge series of videos where we tackle various coding challenges ranging from the beginner level to advanced level - especially in the context of coding interviews.
Any coding problems you would like me to explore? Please let me know in the comments what you think!
#java #interview #javabrains
![Detect Capital - LeetCode Interview Coding Challenge [Java Brains]](http://i.ytimg.com/vi/1VtgflWO7cE/mqdefault.jpg)
![Detect Capital - LeetCode Interview Coding Challenge [Java Brains]](/img/tr.png)
"resultLength = end - begin - 1;"
it is not due to 0 indexing of Java. It is math. While finding inclusive length between two points you have to add 1 to its difference. eg. ZABBAV will be 4 - 1 + 1 = 4 chars long . You did "begin--" and "end++" before you break out of while loop which offsets the begin-end range by 2 units. Your correct start is "begin + 1" and correct end is "end - 1". The inclusive length of the substring thus is (end - 1) - (begin + 1) + 1 (due to inclusive range) which is equal to "end - begin - 1".
Apart form that, a big fan of your teaching. Your tutorials helped me land my current job.
Thanks... That was actually helpful. :)
Found this really helpful !! Thanks :)
This is really helpful
Your comment actually helped to understand the logic behind the value of resultLength.. :)
I rarely reply on CZcams.. but thanks for this!
I watched your previous palindrome video last month on the day before my interview and guess what? I got 4 hackerrank problems to solve and 2 of them were about palindromes !! AND I GOT THE JOB 😍
Thank you sir!
can we get that 4 four hackerrank problems?
@@raniverla2731 I actually don't have access to them now. There were 2 different palindrome ones and some other 2 which I don't remember anymore
good job!
Yeah! Leetcode problems from Java Brains! Can't wait for those incredible explanations haha
Man this is the best explanation for this question, I have been struggling with this from so long. Thanks a lot!!
Thank you for the excellent explanation! Special thanks for the "clean code" and expressive method/variable names-- rare to see that in LeetCode problem solution videos!
Does anyone feel - What the hell I am doing with my life?Is our life all about all these LC codes.....Does this give you fulfillment? Philosophy apart .....Thankyou for the good explanation
It is beautiful if you like solving things. It's practicing your analytical skills and identify patterns. Mathematicians and Physicists use these skills everyday to make things efficient and find solutions. However it's not fun if you don't like practicing/working on algorithms.
The concepts underlying computer science are fascinating, and the applications of programming in solving real-world problems are exciting. Those things draw a lot of people into the field. Unfortunately, we have to pretend to be a parser to get a first round technical interview every time. The further along you are in your career, the more distanced you become from this, so it hits you like a bucket of cold water. You're not alone in the feeling. Fortunately, the interview usually becomes more substantial and conceptual after that, and most languages abstract this stuff away.
I only care about the interview i will not spend not even 1 sec after i get the job
I feel you man, its all part of the game.
It's the stupidest game.
i understand your solution, but i feel like i would have never been able to think of this solution on my own. its discouraging sometimes :( thanks for explaining everything so clearly!
Many are with you, so don't worry. Our practice should make us better hopefully. Good luck!
Bro just learn Manachers algorithm and you will impress if this appears on an interview xD
i always write my own solutions that i understand better, challenge is they might not be efficient
I really love these videos. Your explanations are extremely helpful and easy to understand, please make more!
This explanation was so easy and so well explained. I am really happy I found this video. Thanks, Java Brains !!
Your video really helped. Thank you very much. Just a suggestion: if you can take an example and walk through the solution towards the end, that would be awesome
please keep on these leetcode series they are really helpful and fun to watch.
Very helpful. You have explained it in detail to make it easy for everyone to understand. Thank you!
thanks so much for this explanation, it was very thorough and I was able to understand it. Take my upvote!
Amazing content! Found this explanation very helpful !
You are the most amazing teacher !!
If you have some time try to explain backtracking and DP in simple way as usual.
Thank you so much
Very cool video, as always. One small mistake in your explanation in my opinion. The result length is equal to end - begin - 1 not because zero index but because when one subtracts end - begin, it gives you the difference and not the number of indexes included. For example if we have 1, 2, 3, 4, 5, 6 and begin = 2 and end = 5, the length is still equal to end - begin - 1.
You are amazing! Teacher needs to learn from you how to teach as well.
I am glad I found your videos...:) your explanation actually helps to understand efficient solution ..
I did a very complex solution where there was a nested loop and I put how many times I had a roll it back and it passed every test case. However, it would not be accepted by LeetCode because it runs out of time because it is way too complex. I'm glad I found this video to give me a better way to try it.
Hello, can you tell us what is the Space|Time complexity of this solution please?
Mr Koushik, your tutorial is wonderful. It amazing))). I stuck with one question about spring configuration. Can we reload spring properties in context dynamically without restarting applicatiom? And how to do it. Stack overflow with baeldung tells about Apache PropertiesConfiguration. But how to do it without boot. Only spring core?
Thanks kaushik for such a wonderful explanation , big fan of teaching style
I am still a little confused as to why we are calling expandRange method twice with different set of indices? I am not able to connect the dots. Can you please help me understand? Thank you!
Awesome explanation. :) Thank you sir :)
we are running expandRange twice for even and odd length. Can't we put a check if(length %2) and accordingly call one of them? If we can't then please provide an explanation. Can't find an answer to this
Great!!
Feedback: Do a walkthrough of the code at then end.
Great explanation, thank you!
Thanks for the video. Question. is the time complexity O(n^2) because you loop n times and check very character in every iteration?
the worst case is where every substring is a palindrome... this only happens if you have always the same character, like "aaaaaaaaaaa"... then you have O(N²)
Thanks a lot for the video! Only part which I couldn't understand is why we're doing "end - begin -1" in the if block.
Assume the while loop breaks when begin=2 and end=5. That means the str.charAt(begin)==str.charAt(end) condition was satisfied for begin=3, end=4. The length of the palindromic string then is (4-3+1). If we write it in the current begin and end variable values it will be ( (4-3+1) = (4+1-1)-(2+1)+1 = (5-2-1)) or (end-begin-1)
Please do a video series on Big O Notation and Time Complexity.
awesome explanation. I just implemented your logic with both python and java to practice and understand more.
That's the best explanation for the palindrome.
You are perfect 😍😍😍😍😍
Sir, I am your big fan, I have asked you earlier also please please make a video on saga pattern in java. There is not a single tutorial on youtube implementating saga. Please make a video on that. I will be very thankful to you for this. Atleast mention the time like 6 months chlega
Very well explained. Really helpful
I can listen to you the whole day !! 😍😍
I have the same T Shirt as you are wearing Kaushik.... Thanks for the video :)
Please correct me if I'm wrong but there's no need to call expandRange twice. You can simply check if, and only if, either the character left or right of the center is equal to the center. Because you can only have a palindrome with a 2-character center if both characters at the center are equal, otherwise it's no longer a palindrome.
Yes, I used:
expand(s, i, i);
if(s.charAt(i) == s.charAt(i+1))
expand(s, i, i+1);
And it worked fine for all the testcases.
Hi Koushik, can you please do some spring integration videos for us.
Can someone please tell me why this single line code is not preferred to check if a string is palindrome or not????
return new StringBuilder(s).reverse().toString().equals(s);
we take a string builder and reverse the string and checks if it's same with given string, so why do we have to write our own loops if there is a default function which does this for us?
Nice explanation Kaushik.
Great explanation !!! please do more videos on leetcode sir
great explanation and very clean code
@kaushik , How we know that , expandRange(...) got palindrome string ? This while loop anyway exit at one particular point either at end of index or characters are not equal. ?
I have the same doubt. In some cases, after exiting the loop, the substring might not even be a palindrome, and yet we are storing the start index and the length only because the if condition gets satisfied.
Yes, Even the for loop in the main method he wrote Is wrong , no need of -1there
Awesome, pls create video on time and space complexity
U r great Kaushik!!!
What would be the Time & Space complexity for this algorithm? Isn't it still n^2?
Lovely great explaination do make a course on spring mvc , core
This was my first assignment on my first week on university and my first programming class. I remember being so overwhelmed by it and feeling like it is just impossible to do, now it is more of joke :D
Damn, my first assignment was to get user input do some simple math and string processing and printing the result 😅 thats a harsh first assignment to get
What about if palindrome substring is from 0 to n-2 or n-3 ... index or vice versa
I see you are using apple pen for yor drawing purpose , how you record the screen when you writing ?? :)
This code is not working for “bbbb” this type of string can you please help on this… what condition do we have to change so that with all possible scenarios it will work and this string also it will work?
I thought you mentioned that you would do Node JS videos daily .. eagerly waiting ..
very good explanation to this bit tricky and complex problem
I got this question asked in the first telephonic screening at google.
Thank you, sir.
Thank you for your nice video! There is sth confusing to me. For string "abc", when the loop starts from the first charcter "a", both the right and the left pointer will read from "a" first, but it seems that the "a" will be considered as a valid palindrome substring based on the method expandRange(). Am I wrong here?
You are correct. Each individual character is a palindrome in itself.
awsome , i am eagrly looking zuul api gateway to complet microservices .
thank you very much sir for this video
Thank you so much
please make video on algorithm and data structure.
Please make videos of DP problems like this
Or... Assuming we're looking for normal palindrome words, could we not just split the input string into an array of individual words, check and filter each word based on whether it's a palindrome, then just return the longest of all the found palindrome words?
waiting for more LC..probably a collection...
There exists an algorithm to solve this in O(n) time - Manacher's agorithm. But nice explanation of the O(n^2) solution.
Easy peasy after watching your video🤗. Why don't you post on competitive programming problems? 🙂
is the complexity oN2 right?
Sir .. please make videos on spring 5 webflux
One point is not clear for me. Why are we calling expensdRange() method two times with different parameter? can we put these method in ifElse condition based on String odd/even length?
As we don't have the start and end index, we don't know the string length in advance. Thats why we call it 2 times. As he says we move outwards, not inwards. I hope you get the point.
Hey Kaushik, Good work mate, In case strLength is 2, we can return same string, no need of further processing, Right ?
No. What if the two characters are different? "ab" is not a palindrome. "aa" is.
does he tell us what is run-time/space-time of his algorithm? is its n2 or linear?
for (i=str.length,i>1;i--)
for(j=0; j
Hi koushik
Great explanation but one of my test case is failed. I tried debugging and it is working fine while compiling but when I submit my test case I am getting index out of bound exception: begin 2 , end 8 , length 5 . input= rfkqyuqfjkxy output :r
Awesome !!!!
Hii I am fairly new to Java. i have a small question. Do we not need to instantiate the int we created? like int resultStart=0; int resultLength=0. when the condition 'resultLength < end-start+1' first appears, resultLength does not have a value...
By default, the global instance variable resultLength is implicitly set to 0 when it's first declared I believe. But on Leetcode, you have to be careful with this because the test suite is not always well written. Sometimes, Leetcode will use the same Solution instance object to run through all of its tests, so that means that resultLength and resultStart might not get reset properly to 0 between tests. So if you want to be safe and avoid difficult to find bugs, if you're going to declare global instance variables within the scope of the Solution class, then you also need to explicitly initialize their value to 0 within the body of longestPalindrome() just to be safe.
if the string has odd number of characters, do we still need to call 'expandRange()' twice? if yes, why? Can you please expand on that bit a little more. That's the only thing which seems a bit confusing.
same can some one explain
What if given string is null ?
Good explanation Kaushik.
How does this perform better than O(n^2) ? Arn't you still nesting loops ? Why would this be a better solution ? I don't get it.
Oh i get it, its because we are not looping through the entire string again, rather just through the sub strings ?
good explanation
When you are doing str.charAt(begin) == str.charAt(end) it will check the reference or the actual value? at 18:45 shouldn't we be using equals?
actual value will be checked (there's no ref. variable), from .charAt() you get a char and not String
the method charAt returns a character which is a primitive type/base type hence you can use == for evaluation, unlike reference types
Hey! Thank you so much for the video. I have a doubt. Let us say that we have been given a string "madamefg". In the iteration where begin and end indices are 1, the while loop will be true and begin will become 0 and end will be incremented to 2. In the second iteration, the while loop will not be satisfied, as m != d. However, the if condition will be satisfied, as resultLength will be 0 and end - begin - 1 will be 1, and the resultLength and resultStart will be 0. But, mad is not even a palidrome. Could you please explain how this works?
if you try it out with "mad" you get "m", because the substring has the indices 0 and 1 in the string, if you try "madam" the indices are overriten again with the provided palindrome of a greater length.
"madam" it is a palindrome.
@0:58
comma or apostrophe (') just nitpick'ing :)
You are amazing !
You are awesome!
What if I reverse the String and Check the result with the original?.If the both are same. we will get a Palindrome.Is this way will provide a solution for the above Problem?
Hi Koushik
Can you please explain me the solution for this problem
Given a list of three digit numbers as input write a function that prints unique combination and also their sum
Input = [111 ,121, 131,111,141]
output=[111:3 , 121:4 ,131:5, 141:6] the number after the colon is the sum of those 3 digits and it returned without any duplicates.
Thanks,
Snigdha.
You can use HashMap for this
Can you create a channel for LeetCode challenge? Your explanation way better the Leetcode official solution.
For smallest palindrome substring?
Awesome explanation. Please change your name from java to something else because I kept avoiding your channel because of java😂😂
not sure if its the most efficient way of doing it but kinda works..
public static boolean isPalindrome(String s) {
if(s==""){
return true;
}
String cleanedS = s.replaceAll("[^a-zA-Z0-9]", "");
StringBuilder stringBuilder = new StringBuilder(cleanedS);
StringBuilder reversedString = stringBuilder.reverse();
if (cleanedS.equalsIgnoreCase(reversedString.toString())){
return true;
}
return false;
}
sir now am clearly underStood
actually i misunderstand that if statement bcs of that wiredMath Trick
if am doing below code mean i can understand .tq soMuch sir.
begin++;end--;
if(resultLength
what about the special character avoidance? and what about that N^2 complexity, the for is calling a method with a while within
the worst case is where every substring is a palindrome... this only happens if you have always the same character, like "aaaaaaaaaaa"... then you have O(N²)
How loop starts with middle
Kaushik, Since we want to know the longest palendrome. Why cant we do this?
1) Try to find if the entire string (with length say L) is palendrome.
2) If 1 is not true, check that if out of the two possible strings with length = L - 1, is any one a palendrome.
3) If 2 is not true, check that if out of the three possible strings with length = L - 2, is any one a palendrome.
4) If 3 is not true, check that if out of the four possible strings with length = L - 3, is any one a palendrome.
and so on...
Correct me if I am wrong. The time complexity is O(n2) and space complexity is O(1).
the worst case is where every substring is a palindrome... this only happens if you have always the same character, like "aaaaaaaaaaa"... then you have O(N²)
I would argue that space complexity is the O(N), since you still need to String, I guess you are referring to Auxiliary Space which is O(1), since you only need constant amount of variables and no string duplication.
However there are faster Algorithms running in O(N) time, but with higher space complexity... Boyer-Moore string-search algorithm can be modified, and suffix trees also can solve the problem faster
@@ZapOKill Yeah, I meant auxiliary space complexity.
We can do it in both O(n) and O(n^2) by the way
the worst case is where every substring is a palindrome... this only happens if you have always the same character, like "aaaaaaaaaaa"... then you have O(N²)
❤️❤️❤️❤️
Magic =)
Simple and easy to understand could be:
public class LongestPalindromeInString {
public static void main(String[] args) {
String s = ("1712332181");
String longestPalindrome = "";
if (s == null || s.trim().isEmpty()) {
longestPalindrome="";
}
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
String str = s.substring(i, j + 1);
if (new StringBuilder(str).reverse().toString().equals(str)
&& longestPalindrome.length() < str.length()) {
longestPalindrome = str;
}
}
}
System.out.println("Longest Palindrome Sequence :" + longestPalindrome);
}
}
Is it just me or are we not allowed to reverse a string and compare it to check for a palindrome ....
just want to understand why we have called two times expandRange
i think there are two cases:
1). if the string length is odd, we are going to have a single mid point and serve as initial value for both begin and end.
2).if the string length is even, we can't have a single mid point. so the two midpoints we get will be mid and mid+1,
where mid will serve initial value for begin and mid + 1 as initial value of end.
hope you got my point
This solution is no longer accepted in leetcode.. Guess they add few more test cases.