LeetCode 5: Longest Palindromic Substring Solution
Master LeetCode problem 5 (Longest Palindromic Substring), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
5. Longest Palindromic Substring
Problem Explanation
Explanation
To find the longest palindromic substring, we can use the "expand around center" approach. For each character in the string, we consider it as a center and expand outwards to find the longest palindrome. We handle both odd-length and even-length palindromes separately. The time complexity of this approach is O(n^2) and the space complexity is O(1).
Solution Code
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 5 (Longest Palindromic Substring)?
This page provides optimized solutions for LeetCode problem 5 (Longest Palindromic Substring) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 5 (Longest Palindromic Substring)?
The time complexity for LeetCode 5 (Longest Palindromic Substring) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 5 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 5 in Java, C++, or Python.