Question

Formatted question description: https://leetcode.ca/all/5.html


5	Longest Palindromic Substring

 * Given a string S, find the longest palindromic substring in S.
 * You may assume that the maximum length of S is 1000,
 * and there exists one unique longest palindromic substring.
 *
 * A palindrome is a word, phrase, number, or other sequence of characters
 * which reads the same backward or forward
 *
    Example 1:

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

    Example 2:

    Input: "cbbd"
    Output: "bb"

@tag-string
@tag-dp

Algorithm

First, let me talk about what is a palindrome, that is, a string that reads the same in both front and back, such as “bob”, “level”, “noon” and so on.

Then the longest palindrome substring is the longest palindrome substring in a string. There are five questions about palindrome in LeetCode. Except for this one, the other four are Palindrome Number, Validate Palindrome, Palindrome Partitioning, Palindrome Partitioning II. We know that the traditional method of verifying palindrome is two by two. Symmetric verification is equal, then for the problem of retrieving the text string, it is necessary to use each character as the center, like two-side diffusion to find the palindrome string. The time complexity of this algorithm is O(n*n), and it can be through OJ .

It is to pay attention to the odd and even situation, because the length of the palindrome string can be odd or even, for example, “bob” is the palindrome in odd form, and “noon” is the palindrome in even form. Both forms of palindrome should be searched, for odd numbers Formally, we start from the traversed position as the center and spread to both sides. For even-numbered cases, we treat the current position and the next position as the middle two characters of the even-numbered palindrome, and then search to both sides.

Code

Java

public class Longest_Palindromic_Substring {

    // dynamic programming, note to avoid expensive operation
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }

        int longest = Integer.MIN_VALUE;
        int start = 0;
        int end = 0;

        // initialization, default all false
        // dp[i][j] meaning substring i-j is palindromic
        boolean[][] dp = new boolean[s.length()][s.length()];

        for(int i = 0; i < s.length(); i++) {

        	// @note: for the second pointer j, direction not important, same result
            // for(int j = i; j >= 0; j--) {
            for(int j = 0; j <= i; j++) {

                if(i == j || (s.charAt(i) == s.charAt(j) && i - j < 2) || (s.charAt(i) == s.charAt(j) && dp[i - 1][j + 1])) {
                    dp[i][j] = true;

                    // check max
                    if(i - j + 1 > longest) {
                        // @note: below is expensive, over time
                        // result = s.substring(j, i + 1);
                        longest = i - j + 1;
                        start = j;
                        end = i;
                    }
                }
            }
        }

        return s.substring(start, end + 1);
    }


	// brute force, overtime
	public class Solution2 {
	    public String longestPalindrome(String s) {
	        if(s == null || s.length() == 0) {
	            return "";
	        }

	        String result = "";

	        for(int i = 0; i < s.length(); i++) {
	            for(int j = i + 1; j < s.length(); j++) {
	                String sub = s.substring(i, j + 1);
	                if(isPal(sub) && sub.length() > result.length()) {
	                    result = sub;
	                }
	            }
	        }

	        return result;
	    }

	    public boolean isPal(String s) {
	        char[] array = s.toCharArray();
	        int i = 0;
	        int j = array.length -1;

	        while(i <= j) {
	            if (array[i] != array[j]) {
	                return false;
	            }
	            i++;
	            j--;
	        }

	        return true;
	    }
	}

}

All Problems

All Solutions