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

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

[@robdai]

"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.

[@RavindraKumar17]

Thanks... That was actually helpful. :)

[@harinijeyaraman8789]

Found this really helpful !! Thanks :)

[@shafiaaskari5949]

This is really helpful

[@ankitaburbure8142]

Your comment actually helped to understand the logic behind the value of resultLength.. :)

[@RibenaLion]

I rarely reply on KZbin.. but thanks for this!

[@crteezy]

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!

[@raniverla2731]

can we get that 4 four hackerrank problems?

[@crteezy]

@@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

[@rollinOnCode]

good job!

[@Daniyay]

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!

[@mkbhd2]

Many are with you, so don't worry. Our practice should make us better hopefully. Good luck!

[@Satenc0]

Bro just learn Manachers algorithm and you will impress if this appears on an interview xD

[@ngonimugandani4504]

i always write my own solutions that i understand better, challenge is they might not be efficient

[@SpaceTimeBeing_]

Yeah! Leetcode problems from Java Brains! Can't wait for those incredible explanations haha

[@NimbuCB]

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

[@nameunknown007]

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.

[@MereAYT]

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.

[@GenjaOrigins]

I only care about the interview i will not spend not even 1 sec after i get the job

[@ramfattah275]

I feel you man, its all part of the game.

[@bobweiram6321]

It's the stupidest game.

[@Granta_Omega]

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.

[@prafullakh]

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

[@vinayakgupta1]

Man this is the best explanation for this question, I have been struggling with this from so long. Thanks a lot!!

[@abhijitpatwardhan8406]

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!

[@johnny5gr]

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.

[@annonymousarmadillo1094]

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.

[@aakashgupta7211]

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.

[@MegaValture]

I really love these videos. Your explanations are extremely helpful and easy to understand, please make more!

[@ngonimugandani4504]

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; }

[@ayushisinghal2339]

Very helpful. You have explained it in detail to make it easy for everyone to understand. Thank you!

[@akashchoudhary5895]

great explanation and very clean code

[@TheSumitSagar]

please keep on these leetcode series they are really helpful and fun to watch.

[@shafiaaskari5949]

This explanation was so easy and so well explained. I am really happy I found this video. Thanks, Java Brains !!

[@AmanRaj-tj7lj]

Great!! Feedback: Do a walkthrough of the code at then end.

[@ALEEMKHAWAR1]

Thanks kaushik for such a wonderful explanation , big fan of teaching style

[@knrakeshkumar]

You are amazing! Teacher needs to learn from you how to teach as well.

[@youssefmyh]

That's the best explanation for the palindrome. You are perfect 😍😍😍😍😍

[@RaviAdhav]

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...

[@sriraghavsira7149]

Please do a video series on Big O Notation and Time Complexity.

[@vartikasingh6812]

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

[@divitvivit8803]

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); } }

[@jordanhumphrey6379]

thanks so much for this explanation, it was very thorough and I was able to understand it. Take my upvote!

[@kartikenbarnwal]

I can listen to you the whole day !! 😍😍

[@Granta_Omega]

This still is an n-squared solution, but I guess that's the best it can be.

[@chandrakanthdudela5515]

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.

[@evolvingnoobninja2431]

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)

[@bewareofnikhil]

There exists an algorithm to solve this in O(n) time - Manacher's agorithm. But nice explanation of the O(n^2) solution.

[@alittlecoding]

awesome explanation. I just implemented your logic with both python and java to practice and understand more.

[@ankitaburbure8142]

I am glad I found your videos...:) your explanation actually helps to understand efficient solution ..

[@kuttikrishnankodoth1463]

I see you are using apple pen for yor drawing purpose , how you record the screen when you writing ?? :)

[@arunprasanth9527]

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

[@nirmalm80]

Great explanation !!! please do more videos on leetcode sir

[@harinijeyaraman8789]

Amazing content! Found this explanation very helpful !

[@dev-skills]

I got this question asked in the first telephonic screening at google.

[@todortotev]

Great explanation, thank you!

[@harshitsaluja3809]

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.

[@deliveringIdeas]

Any luck so far?

[@Anubis10110]

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

[@bhavinpatel5119]

Very well explained. Really helpful

[@samahome]

very good explanation to this bit tricky and complex problem

[@sithumdilanga650]

Thank you so much

[@zoel.9537]

Can you create a channel for LeetCode challenge? Your explanation way better the Leetcode official solution.

[@sachinmittal968]

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

[@findarpit92]

Awesome explanation. :) Thank you sir :)

[@davinderpalsingh6412]

Nice explanation Kaushik.

[@vaishnavi_cholli]

good explanation

[@ghanshyamkhatri3541]

U r great Kaushik!!!

[@pitchaiahbheemanapally2338]

What if given string is null ? Good explanation Kaushik.

[@user-vx5sn9nw4u]

I will do technical interview on Wednesday, hope i will got that type question

[@Java.Brains]

Good luck!

[@don300100]

I have the same T Shirt as you are wearing Kaushik.... Thanks for the video :)

[@91-ritikjain36]

I Watched all your video and i am not able to understand even an single question

[@mrOverdue]

What about if palindrome substring is from 0 to n-2 or n-3 ... index or vice versa

[@aakashgupta7211]

What would be the Time & Space complexity for this algorithm? Isn't it still n^2?

[@elukok]

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

[@williaamlarsson]

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

[@nathansnow]

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?

[@parambharti7095]

Awesome !!!!

[@findarpit92]

Please make videos of DP problems like this

[@ruchibhadani6920]

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

[@malikwaseem1983]

You are awesome!

[@dnavas7719]

Thanks for the video. Question. is the time complexity O(n^2) because you loop n times and check very character in every iteration?

[@ZapOKill]

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²)

[@salmankevin7205]

Easy peasy after watching your video🤗. Why don't you post on competitive programming problems? 🙂

[@shashankjakhmola6226]

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?

[@testingDhippiuh]

Thank you, sir.

[@taslimapatel5960]

You are amazing !

[@saddamahmad2310]

thank you very much sir for this video

[@pranavchaudhary264]

does he tell us what is run-time/space-time of his algorithm? is its n2 or linear?

[@AmitToor]

for (i=str.length,i>1;i--) for(j=0; j

[@sanskritinannore7209]

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

[@kaliraj5659]

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?

[@chetanbhandari3033]

Awesome, pls create video on time and space complexity

[@dr.downvote]

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?

[@sarthaksrivastav3408]

Awesome explanation. Please change your name from java to something else because I kept avoiding your channel because of java😂😂

[@sivasurendranath7734]

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.

[@sivasurendranath7734]

Oh i get it, its because we are not looping through the entire string again, rather just through the sub strings ?

[@trungle-gn6bw]

It's not a efficient approach, you can try to use Rolling-hash

[@Aapla_Institute]

awsome , i am eagrly looking zuul api gateway to complet microservices .

[@momann4394]

9:50 - For those who already know the O(n^2) solution is bad

[@shredder_plays]

Lovely great explaination do make a course on spring mvc , core

[@user-bd8nj4th8c]

Hi Koushik, can you please do some spring integration videos for us.

[@oluwarotimiadeola1997]

Is it just me or are we not allowed to reverse a string and compare it to check for a palindrome ....

[@aasthachauhan4385]

is the complexity oN2 right?

[@bthakur3870]

Hey Kaushik, Good work mate, In case strLength is 2, we can return same string, no need of further processing, Right ?

[@umangjain5460]

No. What if the two characters are different? "ab" is not a palindrome. "aa" is.

[@shikharchaudhary6984]

We can do it in both O(n) and O(n^2) by the way

[@ZapOKill]

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²)

[@ena81xx]

Such a cheat! This is Nick White's solution.

[@amargupta1728]

please make video on algorithm and data structure.

[@snigdhamadhuri3133]

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.

[@HanilKathuria]

You can use HashMap for this

[@senthilkumaran5317]

Hello, can you tell us what is the Space|Time complexity of this solution please?

[@you.tube12818]

I thought you mentioned that you would do Node JS videos daily .. eagerly waiting ..

[@GomboevRL]

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?

[@pandupvpk]

waiting for more LC..probably a collection...

[@umangjain5460]

Correct me if I am wrong. The time complexity is O(n2) and space complexity is O(1).

[@ZapOKill]

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

[@umangjain5460]

@@ZapOKill Yeah, I meant auxiliary space complexity.

[@ArjunKalidas]

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!

[@AmitKumar-hn7qh]

How loop starts with middle

[@rahulsaxena9103]

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.

[@getrogo4474]

same can some one explain

[@xilongzhang6856]

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...

[@stephanbranczyk8306]

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.

[@gomezvillegasdaniel]

what about the special character avoidance? and what about that N^2 complexity, the for is calling a method with a while within

[@ZapOKill]

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²)

[@sumansatpathy2862]

Sir .. please make videos on spring 5 webflux

[@vikashtiwari2136]

For smallest palindrome substring?

[@biswajit_rout_369]

❤️❤️❤️❤️

[@ramfattah275]

13:54 haha brain fart