LeetCode problem 5#: Longest Palindromic Substring

LeetCode’s Problem #5, “Longest Palindromic Substring”, is a classic challenge that tests one’s understanding of strings and dynamic programming. A palindrome is a string that reads the same forward and backward, and this problem requires finding the longest palindromic substring within a given string.

Understanding the Problem

Given a string s, find the longest substring which is a palindrome. For example, if s = "babad", the function should return “bab” (note that “aba” is also a correct answer).

Approach and Algorithm

A common approach to solve this problem is to use dynamic programming. The idea is to create a table dp where dp[i][j] will be true if the string from index i to j is a palindrome.

Alternatively, a more intuitive approach is to expand around each character (and each pair of characters, for even-length palindromes) and see how far we can extend the palindrome.

Java Solution

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

}

Python Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expandAroundCenter(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        if not s or len(s) < 1:
            return ""
        start, end = 0, 0
        for i in range(len(s)):
            len1 = len(expandAroundCenter(i, i))
            len2 = len(expandAroundCenter(i, i + 1))
            maxLen = max(len1, len2)
            if maxLen > end - start:
                start = i - (maxLen - 1) // 2
                end = i + maxLen // 2
        return s[start:end + 1]

Conclusion

The Longest Palindromic Substring problem is a great exercise to improve your understanding of string manipulation and dynamic programming. Both the Java and Python solutions provided use the method of expanding around the center, which is more intuitive and often more efficient than the dynamic programming approach. As with many LeetCode problems, practicing and understanding different approaches to a problem can greatly enhance your problem-solving skills in programming.