Longest Palindromic Sub-string (LeetCode 5) | Full solution with examples | Study Algorithms

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:

💻 Get Social 💻

#leetcode #programming #tutorial

[parthnoida]

Finally someone is focusing on the algorithm rather than implementation

[plutomessi]

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

[_KULDEEPCHOUDHARY]

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

[kah]

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 🙃

[callmeMr.X]

CORRECT CODE ✅✅
You have passed wrong paramter in substring(), it should be high - low - 1;

string expand(string str, int low, int high) {
while (str[low] == str[high]) {
low--;
high++;

if (low == -1 || high == str.length())
break;
}
// substring length = high - 1 - (low + 1) + 1 = high - low - 1
return str.substr(low + 1, high - low - 1);
}

string longestPalindrome(string str) {
if (str.length() <= 1)
return str;
string palindrome = "", longestPalindrome = "";
for (int i = 1; i < str.length(); i++) {
// Consider odd length
palindrome = expand(str, i, i);
if (palindrome.length() > longestPalindrome.length()) {
longestPalindrome = palindrome;
}
// Consider even length
palindrome = expand(str, i - 1, i);
if (palindrome.length() > longestPalindrome.length()) {
longestPalindrome = palindrome;
}
}
return longestPalindrome;
}

[SHRIRAM-sgwh]

We have to define "Terminating condition(line 20-22) " after capturing longest Palindrome(Line 25-29) So it will resolve string like s="ac"; beacuse LPS will never be updated if we get high==str.length() because while loop breaks there .

[mohdahasansiddiqui]

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

[technicalstuff]

string palindrome should be :
string palindrome=str.substr(low+1, high-low-1);

[JustMeItsMMN]

Thank you very much for this amazing explanation

[amitprasadiitg]

I believe in CPP string palindrome should be
string palindrome=str.substr(low+1, high-low-1);

[suranjankarmakar]

How could i optimise its time complexity?

[mjjtube]

Great tutorial bud, but could you please explain why we start with low = -1 for even length?

[investigopedia]

The Time Complexity of this approach will be O(str.length()^2) I guess.

[pranaypampana]

here is the code

class Solution {
public String longestPalindrome(String s) {
if (s.length() <= 1) return s;

String lps = "";

for (int i = 1; i < s.length(); i++) {
// Odd length palindromes
int low = i;
int 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
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;
}
}

[gokulakannan]

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' ?

[SuriyaT]

any one pls clarify me why HIGH is used in substring(),

[AdityaAgrawal-finp]

bhaiya ittna acha mat padaho mera faang clear ho jaega

[Ajeetkumar-uohf]

Bhai solution khol ke kya bata rha hai code ni karne ata kya😂