Given a string s, find the longest substring in s. You can assume that s is at most 1000.

Example:

Input:"babad"Output:"bab"Note:"aba"That's a valid answerCopy the code

Example:

Input:"cbbd"Output:"bb"
Copy the code

Train of thought

The original idea is to do it the dumbest way possible, which is to find all the strings and then palindrome all the substrings and record the length. You can imagine the time complexity of this, O(n) times O(n) times O(n)=O(n^3). So this kind of affirmation can’t meet our requirements.

Ok, so let’s analyze this problem, and let’s specialize this problem;

  • Suppose the input string length is 1

    So the longest palindrome of this string is itself, length 1

  • If the string is of length 2, it requires that the two characters be equal if it is a palindrome string.

    That is: s[I] == s[j] and i-j=1(here I is assumed to be the larger index position)

  • What if I minus j is greater than 1? Is it ok to meet the following conditions as long as:

    That is: S [I] == S [j] &&S [i-1] == S [j+1]

The idea is dynamic programming. The theoretical text on dynamic programming is not code, interested partners wide to learn by themselves. Here is the code for this problem:

public String longestPalindrome(String s) {
    // A string of length 1 returns the current string
    if (s.length()==1) {return s;
    }
    // If the length is 2 and the two characters are equal, return
    if (s.length()==2&&s.charAt(0)==s.charAt(1)) {return s;
    }
    // isLongestPalindrome[j][I]
    // isLongestPalindrome[1][5] = = true indicates that the substring from 1 to 5 is a palindrome.
    boolean[][] isLongestPalindrome = new boolean[s.length()][s.length()];
    // The longest palindrome string starts with a maximum of 0
    int maxlen = 0;
    // Start index position for maxlen
    int beginIndex = 0;
    // The end index position for maxlen
    int lastIndex = 0;
    for (int i=0; i<s.length(); i++){int j=i;
        while(j>=0) {// The third condition above is satisfied, i.e. the current s.charat (I)== s.charat (j) and
            // and s[j+1 to i-1] is also a palindrome string
            if (s.charAt(i)==s.charAt(j)&&(i-j<2||isLongestPalindrome[j+1][i-1])){
                isLongestPalindrome[j][i]=true;
                if (maxlen < i-j+1) {
                    beginIndex = j;
                    lastIndex = i+1;
                    maxlen = i-j+1; } } j--; }}return s.substring(beginIndex,lastIndex);
}
Copy the code