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

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

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

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

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

[@vinayakgupta1]

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

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

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

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

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

[@kuttikrishnankodoth1463]

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

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

[@MegaValture]

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

[@sriraghavsira7149]

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

[@ALEEMKHAWAR1]

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

[@TheSumitSagar]

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

[@ayushisinghal2339]

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

[@aakashgupta7211]

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

[@bewareofnikhil]

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

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

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

[@youssefmyh]

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

[@AmanRaj-tj7lj]

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

[@shafiaaskari5949]

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

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

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

[@ankitaburbure8142]

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

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

[@naikuoyang6071]

He said, you can loop loop loop, but...

[@kartikenbarnwal]

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

[@alittlecoding]

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

[@akashchoudhary5895]

great explanation and very clean code

[@jordanhumphrey6379]

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

[@dev-skills]

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

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

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

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

[@zoel.9537]

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

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

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

[@senthilkumaran5317]

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

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

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

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

[@nirmalm80]

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

[@rmiliming]

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?

[@aakashgupta7211]

You are correct. Each individual character is a palindrome in itself.

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

[@Granta_Omega]

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

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

[@knrakeshkumar]

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

[@pitchaiahbheemanapally2338]

What if given string is null ? Good explanation Kaushik.

[@dear_prit]

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?

[@pradeepwarade3669]

actual value will be checked (there's no ref. variable), from .charAt() you get a char and not String

[@abukasozi295]

the method charAt returns a character which is a primitive type/base type hence you can use == for evaluation, unlike reference types

[@findarpit92]

Please make videos of DP problems like this

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

[@VikasKumar-wh2om]

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?

[@Akshay-tj9hm]

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.

[@aasthachauhan4385]

is the complexity oN2 right?

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

[@harinijeyaraman8789]

Amazing content! Found this explanation very helpful !

[@473-i1m]

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

[@todortotev]

Great explanation, thank you!

[@samahome]

very good explanation to this bit tricky and complex problem

[@noushadh1109]

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

[@sheshashankar8304]

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.

[@naveengs2001]

Yes, Even the for loop in the main method he wrote Is wrong , no need of -1there

[@bhavinpatel5119]

Very well explained. Really helpful

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

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

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

[@davinderpalsingh6412]

Nice explanation Kaushik.

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

[@ghanshyamkhatri3541]

U r great Kaushik!!!

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

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

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

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

[@momann4394]

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

[@findarpit92]

Awesome explanation. :) Thank you sir :)

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

[@metra_s]

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

[@Java.Brains]

Good luck!

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

[@vikashtiwari2136]

For smallest palindrome substring?

[@salmankevin7205]

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

[@sheshashankar8304]

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?

[@mirageman2]

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.

[@nozzhard]

"madam" it is a palindrome.

[@sumansatpathy2862]

Sir .. please make videos on spring 5 webflux

[@oluwarotimiadeola1997]

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

[@interviewprep6827]

This solution is no longer accepted in leetcode.. Guess they add few more test cases.

[@you.tube12818]

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

[@trungle-gn6bw]

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

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

[@AmitKumar-hn7qh]

How loop starts with middle

[@vaishnavi_cholli]

good explanation

[@amargupta1728]

please make video on algorithm and data structure.

[@sarthaksrivastav3408]

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

[@Aapla_Institute]

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

[@sithumdilanga650]

Thank you so much

[@ena81xx]

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

[@chetanbhandari3033]

Awesome, pls create video on time and space complexity

[@don300100]

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

[@taslimapatel5960]

You are amazing !

[@ShubhamSharma1210]

just want to understand why we have called two times expandRange

[@turnRight236]

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

[@malikwaseem1983]

You are awesome!

[@saddamahmad2310]

thank you very much sir for this video