[LeetCode] 5. Longest Palindromic Substring

Posted on | In

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

Explanation

  1. If input string has length less than 2, simply return the string.

  2. To find palindromic string, we can loop through the input string character and each character we make it as the middle of the palindromic.

  3. Palindrom has 2 situations: First situation, abcba, here, c is the middle; Second situation, abba, here, bb is the middle.

  4. In each iteration, we make the current character as the middle. We need to check if the current character is the same as its next character, if not the same, then we consider first situation; else, we consider the second situation.

  5. We can define left and right pointing the middle characters. In the fist situation, left and right are c. In the second situation, left is first b, right is second b.

  6. Then, we compare the middle’s left character and middle’s right character, in other words, str[left-1] comparing to str[right+1]. While they are the same, left = left-1 and right=right+1. After the while loop, left is pointing at the palindrome’s beginning index, and right is pointing at the palindrome’s last index. right-left+1 is its length. At the end of each iteration, we update the maximum length.

  7. After we finish the loop using the last index of the string as middle, we can return the longest pralindrome substring using the left and its maximum length.

Solution 1

(Time: $O(n^2)$; Space: $O(1)$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2)
            return s;
        int start = 0, maxLen = 0, n = s.length();
        int i = 0;
        while (i < n) {
            int left = i, right = i;
            
            while (right+1 < n && s.charAt(right) == s.charAt(right+1))
                right++;

            i = right + 1;

            while (left - 1 >= 0 && right + 1 < n && 
                s.charAt(left - 1) == s.charAt(right + 1)) {
                left--;
                right++;
            }
            
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
        }
        return s.substring(start, start + maxLen);
    }
}

Solution 2

(Dynamic Programming Time: $O(n^2)$; Space: $O(n^2)$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        int start = 0, maxLen = 1, n = s.length();
        boolean[][] dp = new boolean[n][n];
        
        for (int right = 0; right < n; right++) {
            for (int left = 0; left < right; left++) {
                if (right-left == 1 && s.charAt(left) == s.charAt(right)) {
                    dp[left][right] = true;
                } else if (right-left >= 2 && 
                    s.charAt(left) == s.charAt(right) && 
                    dp[left+1][right-1]) {
                    dp[left][right] = true;
                }

                if (dp[left][right] && right-left+1 > maxLen) {
                    maxLen = right-left+1;
                    start = left;
                }
            }
            dp[right][right] = true;
        }
        return s.substring(start, start+maxLen);
    }
}