Leetcode 5. Longest Palindromic Substring

Problem explanation:

The problem requires finding the longest palindromic substring in a string input. A palindromic string is a string that reads the same backwards as forwards, like "level" or "madam". If the input string is "babad", the longest palindromic substring is "bab" or "aba". If the input string is "cbbd", the longest palindromic substring is "bb". The solution should return the palindromic substring in the input string that has the greatest length.

Let's take an example where the input string is "babad". Here, we can find two palindromic substrings which are "bab" and "aba". Both have the same length so we can take any one of them as the output.

Solution approach:

The solution uses the expand around center approach by considering every index in the string as a possible center of palindrome. For each index, two checks are performed - one for odd length palindrome and the other for even length palindrome. It keeps track of the longest palindrome found so far. Finally, it returns the longest palindromic substring.

The way it checks for both odd and even length is because a palindrome can be centered on a letter (for odd length) or a gap between letters (for even length).

The function extend() will check for palindrome from the center to the ends. It continues until the characters on both ends are equal. When they are no longer equal, it exits and returns the start and end indices of the longest palindrome in the string.

For instance, while solving for a string "babad", the function checks the string centered on each character, i.e., 'b', 'a', 'b', 'a', 'd' and also on the gap between every two characters.

Let's observe this with 'b' in 'babad'. When we expand around the center 'b' at index 0, we realize it's a palindrome itself but it isn't the longest. Moving on to the next 'a', we expand and discover that 'aba' or 'bab' are palindromes and these are the longest palindromes in the string 'babad'.

Python Solution:

1
2python
3class Solution:
4    def longestPalindrome(self, s: str) -> str:
5        def expand(left: int, right: int) -> str:
6            while left >= 0 and right < len(s) and s[left] == s[right]:
7                left -= 1
8                right += 1
9            return s[left + 1:right]
10
11        if len(s) < 2 or s == s[::-1]:
12            return s
13        
14        result = ''
15        for i in range(len(s) - 1):
16            result = max(result,
17                         expand(i, i + 1),
18                         expand(i, i + 2),
19                         key=len)
20        return result

Here, the function expand() checks if the string is the same when read in reverse and returns the substring accordingly. Then, the function longestPalindrome() returns the longest palindrome present in the string input.

In the case of the use of list/dictionary, always ensure to check if they are empty or not. If it is not checked, it can lead to an edge case failure that throws an error when the list/dictionary is called but is empty.# JavaScript Solution:

1
2javascript
3var longestPalindrome = function(s) {
4    if (s.length < 2 || s == s.split('').reverse().join('')) {
5        return s;
6    }
7    let start = 0, end = 0;
8    for (let i = 0; i < s.length; i++) {
9        let len1 = expandAroundCenter(s, i, i);
10        let len2 = expandAroundCenter(s, i, i+1);
11        let len = Math.max(len1, len2);
12        if (len > end - start) {
13            start = i - Math.floor((len - 1) / 2);
14            end = i + Math.floor(len / 2);
15        }
16    }
17    return s.slice(start, end+1)
18
19    function expandAroundCenter(s, left, right) {
20        while (left >= 0 && right < s.length && s[left] == s[right]) {
21            left--;
22            right++;
23        }
24        return right - left - 1;
25    }
26};

In this JavaScript solution, the concept remains the same as that of the Python solution. The function expandAroundCenter() is used to check the length of the palindrome by extending in both directions from the center, i.e., every index of the string. The longest length palindromic substring is then sliced from the string and returned.

Java Solution:

1
2java
3class Solution {
4    private int start, maxLength;
5    
6    public String longestPalindrome(String s) {
7        int len = s.length();
8        if (len < 2) {
9            return s;
10        }
11        for (int i = 0; i < len - 1; i++) {
12            expandAroundCenter(s, i, i);  //assume odd length
13            expandAroundCenter(s, i, i + 1); //assume even length
14        }
15        return s.substring(start, start + maxLength);
16    }
17
18    private void expandAroundCenter(String s, int left, int right) {
19        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
20            if (right - left + 1 > maxLength) {
21                maxLength = right - left + 1;
22                start = left;
23            }
24            left--;
25            right++;
26        }
27    }
28}

This Java solution uses a similar concept too. It uses expandAroundCenter() method to validate whether the string is a palindrome by continually expanding to both the ends. The start and maxLength variables are global and indicate the start of the substring and the length of the maximum palindrome. Once we find a palindrome that is longer than the previously saved one, we update the start and maxLength. Finally, the substring is extracted from the main string using its start index and length.

All three solutions manage to solve the problem using the same logic but different language syntax and functionalities. This approach ensures that for every possible center in the string, we are checking for both even and odd-length palindromes which is a comprehensive way to solve this problem.


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ