Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]
ฝัง
- เผยแพร่เมื่อ 11 ก.พ. 2025
- 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/p...
Solution Gist: gist.github.co...
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)
![จากรุ่นใหญ่สุดรวยในเกม FIVEM สู่การติดคุกแก๊งแตกในชีวิตจริง [สรุปแก๊งOREO]](http://i.ytimg.com/vi/Vjj8EX4qpiU/mqdefault.jpg)
"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 TH-cam.. 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!
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
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.
Man this is the best explanation for this question, I have been struggling with this from so long. Thanks a lot!!
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.
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
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!
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.
I really love these videos. Your explanations are extremely helpful and easy to understand, please make more!
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.
Thanks kaushik for such a wonderful explanation , big fan of teaching style
Very helpful. You have explained it in detail to make it easy for everyone to understand. Thank you!
I can listen to you the whole day !! 😍😍
please keep on these leetcode series they are really helpful and fun to watch.
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 😍😍😍😍😍
This explanation was so easy and so well explained. I am really happy I found this video. Thanks, Java Brains !!
thanks so much for this explanation, it was very thorough and I was able to understand it. Take my upvote!
I am glad I found your videos...:) your explanation actually helps to understand efficient solution ..
Great!!
Feedback: Do a walkthrough of the code at then end.
You are amazing! Teacher needs to learn from you how to teach as well.
Great explanation !!! please do more videos on leetcode sir
I Watched all your video and i am not able to understand even an single question
Please do a video series on Big O Notation and Time Complexity.
Great explanation, thank you!
Amazing content! Found this explanation very helpful !
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)
great explanation and very clean code
U r great Kaushik!!!
Very well explained. Really helpful
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...
He said, you can loop loop loop, but...
There exists an algorithm to solve this in O(n) time - Manacher's agorithm. But nice explanation of the O(n^2) solution.
I see you are using apple pen for yor drawing purpose , how you record the screen when you writing ?? :)
I got this question asked in the first telephonic screening at google.
Awesome explanation. :) Thank you sir :)
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;
}
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
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
very good explanation to this bit tricky and complex problem
Nice explanation Kaushik.
This still is an n-squared solution, but I guess that's the best it can be.
Can you create a channel for LeetCode challenge? Your explanation way better the Leetcode official solution.
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);
}
}
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
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
What if given string is null ?
Good explanation Kaushik.
9:50 - For those who already know the O(n^2) solution is bad
Understanding the solution is not a problem but if every problem has its own way and it needs to be looked at like this how can someone come up with a solution at interview time with so much limited time frame unless they have already done it and know the solution.
This is so demotivating.
Any luck so far?
Easy peasy after watching your video🤗. Why don't you post on competitive programming problems? 🙂
Thank you so much
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
Awesome explanation. Please change your name from java to something else because I kept avoiding your channel because of java😂😂
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?
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?
Such a cheat!
This is Nick White's solution.
good explanation
Awesome !!!!
Please make videos of DP problems like this
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²)
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.
thank you very much sir for this video
You are awesome!
You are amazing !
I have the same T Shirt as you are wearing Kaushik.... Thanks for the video :)
Is it just me or are we not allowed to reverse a string and compare it to check for a palindrome ....
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
What would be the Time & Space complexity for this algorithm? Isn't it still n^2?
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
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 ?
What about if palindrome substring is from 0 to n-2 or n-3 ... index or vice versa
Awesome, pls create video on time and space complexity
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?
awsome , i am eagrly looking zuul api gateway to complet microservices .
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!
I will do technical interview on Wednesday, hope i will got that type question
Good luck!
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?
@0:58
comma or apostrophe (') just nitpick'ing :)
Free advice for all smart people : start from 9:44 😁
Thank you, sir.
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?
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.
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.
Hi Koushik, can you please do some spring integration videos for us.
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
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.
I thought you mentioned that you would do Node JS videos daily .. eagerly waiting ..
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
is the complexity oN2 right?
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
please make video on algorithm and data structure.
The follow up code of this for the leetcode question 5 would be:
class Solution {
int start=0;
int end=0;
int maxLen=0;
public String longestPalindrome(String s) {
if(s.length() < 2){
return s;
}
for(int i=0;i=0 && last
Lovely great explaination do make a course on spring mvc , core
It's not a efficient approach, you can try to use Rolling-hash
Hello, can you tell us what is the Space|Time complexity of this solution please?
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.
This solution is no longer accepted in leetcode.. Guess they add few more test cases.
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²)
Sir .. please make videos on spring 5 webflux
❤️❤️❤️❤️