Longest Palindromic Sub-string (LeetCode 5) | Full solution with examples | Study Algorithms
Vložit
- čas přidán 26. 07. 2024
- Longest Palindromic Substring is a programming challenge on LeetCode. A palindrome is a type of string that reads the same when reading left to right and right to left. An example of a palindrome can be “level”, “racecar”, “kayak” etc. Given a string, find the longest palindromic sub-string. You need to return just one string, and the characters should be contiguous. Watch the video to understand the problem in a simplified manner. I then work along with you to solve it first using a Brute Force approach, and then an efficient approach. All along with visuals and explanations.
00:00 - Intro
01:40 - Problem Statement and Test Case
02:58 - Brute Force Solution
03:45 - Efficient Solution
05:41 - Dry-run of code
📚 Links I talk about in the video:
Actual problem on LeetCode: leetcode.com/problems/longest...
Code on Github: github.com/nikoo28/java-solut...
Test cases on GitHub: github.com/nikoo28/java-solut...
📘 A text based explanation is available at: studyalgorithms.com/string/lo...
To see more videos like this, you can show your support on www.buymeacoffee.com/studyalg...
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
#leetcode #programming #tutorial
nikhil bhaiya, please never get demotivated by any negative comment's. I respect every second you have spent on your precious video's for the benefit of community. Thank you so much
thanks for your kind words...trying my best each day!! :)
Finally someone is focusing on the algorithm rather than implementation
I usually don't comment on videos, but the way you explain concepts and approach the problem is phenomenal, keep it up brother 💯
Ignore the negative comments 🙃
Great tutorial sir!
great and understandable Solution
Thank you very much for this amazing explanation
Really helpful!!!
Thanks to you !!
Very neat explanation sir , Thank You
Amazing man🔥
Sir you are the best 🙏🙏🙏🙏🙏
Your voice is so cool, listenable 🥰
will it work for "ab" and "bb"?
I think we should add this extra line as well.
if (str.length() == 2) {
return str.charAt(0) == str.charAt(1) ? str : str.charAt(0) + "";
}
Thanks
expaination is ...Lit !!!!!!!!!!!!!!!
string palindrome should be :
string palindrome=str.substr(low+1,high-low-1);
In a case where no palindrome substring is found then it will return the second char as string, But the function should return first char as string.
Ex . str ="rfvym "
Expected Output : "r"
Original Output:"f"
so for this we need add one condition at the end
if(LPS.length()==1)
return str.substring(0,1)
else
return LPS
the best
How could i optimise its time complexity?
The Time Complexity of this approach will be O(str.length()^2) I guess.
Great tutorial bud , but could you please explain why we start with low = -1 for even length?
we cannot have single midpoint for odd length string
Which headset are you using?
Jabra Evolve 65
any one pls clarify me why HIGH is used in substring(),
String.substring() is a java function which takes two arguments, starting index(inclusive) and ending index (not inclusive) and returns the subtring from the given string. In C++ its starting postion and the size of required substring.
This is because substring return the value from start index to lastindex -1 postion. If we give HIGH -1. it will miss one character@@abhisheknandann
String palindrome = str.subString(low+1, high);
Anyone plz explain.... why he put 'low+1' instead of 'low'
and 'high' is excluding one.... so, he have put 'high+1' but... he put 'high' ?
in subString method, begin index is inclusive and end index is exclusive
while loop terminates when "low" variable and "high" index characters don't match. According to the problem we need palindromic substring so we make "low" increament by one this ensures that the sub string is palindromic.
What is time complexity here?
o(n)2(square) I think
"ab" ka output kya aayega?
Either a or b
@@nikoo28 not working for ab and aa we need to handle that test case
why start for loop with 1
The logic of the solution is that you start at any character and then go both left and right directions. If you start at 0th element, then you cannot go left, only go right. So you will not be able to check palindromes.
@@nikoo28 thanks for wonderful explanation
here is the code
class Solution {
public String longestPalindrome(String s) {
if (s.length() = 0 && high < s.length() && s.charAt(low) == s.charAt(high)) {
low--;
high++;
}
// low and high have gone one step too far, adjust for the correct substring
String palindrome = s.substring(low + 1, high);
if (palindrome.length() > lps.length()) {
lps = palindrome;
}
// Even length palindromes
low = i - 1;
high = i;
while (low >= 0 && high < s.length() && s.charAt(low) == s.charAt(high)) {
low--;
high++;
}
// low and high have gone one step too far, adjust for the correct substring
palindrome = s.substring(low + 1, high);
if (palindrome.length() > lps.length()) {
lps = palindrome;
}
}
return lps;
}
}
Time complexity ki dhajiya udh gayi 😂
Bhai solution khol ke kya bata rha hai code ni karne ata kya😂
if you understand the logic, writing code in any language isn't a problem. I go over the entire concept on how to approach the problem