# Longest Palindromic Substring

`Dynamic Programming`, `String`

Medium

## Question

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.

**Example**

Given the string = `"abcdzdcab"`, return `"cdzdc"`.

**Challenge**

O(n^2) time is acceptable. Can you do it in O(n) time.

**Tags**

String

**Related Problems**

Easy Valid Palindrome 22 %\
Medium Longest Palindromic Substring 26 %\
Medium Palindrome Partitioning II 22 %

## Analysis

### 区间类动态规划

Time O(n^2), Space O(n^2)

用`dp[i][j]`来存DP的状态，需要较多的额外空间: Space O(n^2)

DP的4个要素

* **状态：**
  * `dp[i][j]`: `s.charAt(i)`到`s.charAt(j)`是否构成一个Palindrome
* **转移方程**：
  * `dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])`
* **初始化：**
  * `dp[i][j] = true` when `j - i <= 2`
* **结果：**
  * 找 `maxLen = j - i + 1;`，并得到相应longest substring： `longest = s.substring(i, j + 1);`

### 中心扩展

这种方法基本思想是遍历数组，以其中的1个元素或者2个元素作为palindrome的中心，通过辅助函数，寻找能拓展得到的最长子字符串。外层循环 O(n)，内层循环O(n)，因此时间复杂度 Time O(n^2)，相比动态规划二维数组存状态的方法，因为只需要存最长palindrome子字符串本身，这里空间更优化：Space O(1)

### Manacher's Algorithm

这种算法可以达到O(n)时间，但是并不很通用，因此这里略过讨论。具体参考：

* [Wikipedia: Longest palindromic substring](https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher.27s_algorithm)
* [Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 1](https://github.com/aaronice/lintcode/tree/bbbb974440d4233e80bad25778c3733867e871db/dynamic_programming/www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/README.md)

## Solution

区间DP，Time O(n^2) Space O(n^2)

```java
public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
     public String longestPalindrome(String s) {
         if(s == null || s.length() <= 1) {
             return s;
         }

         int len = s.length();
         int maxLen = 1;
         boolean [][] dp = new boolean[len][len];

         String longest = null;
         for(int k = 0; k < s.length(); k++){
             for(int i = 0; i < len - k; i++){
                 int j = i + k;
                 if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])){
                     dp[i][j] = true;

                     if(j - i + 1 > maxLen){
                        maxLen = j - i + 1;
                        longest = s.substring(i, j + 1);
                     }
                 }
             }
         }

         return longest;
     }
}
```

#### **DP - Time O(n^2), Space O(n^2)**

**外层循环区间长度，内层循环区间起点**

```java
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String longestPStr = "";
        int strLen = s.length();
        boolean[][] dp = new boolean[strLen][strLen];
        for (int len = 1; len <= strLen; len++) {
            for (int i = 0; i < strLen; i++) {
                int j = i + len - 1;
                if (j >= strLen) {
                    break;
                }
                dp[i][j] = (len <= 2 || dp[i + 1][j - 1]) && s.charAt(i) == s.charAt(j);
                if (dp[i][j] && len > longestPStr.length()) {
                    longestPStr = s.substring(i, j + 1);
                }
            }
        }
        return longestPStr;
    }
}
```

#### \***Another implementation DP - Time O(n^2), space O(n^2)**

**外层循环区间起点，内层循环区间终点**

> 递推公式中可以看到，首先知道了 `i + 1` 才会知道 `i` ，所以只需要倒着遍历`i`就行了。
>
> 类似的，先知道`j - 1`才知道`j`，因此顺着遍历`j`

```
In the state transfer function: j - i < 2 could also be j - i <= 2
```

```java
public String longestPalindrome(String s) {
    int n = s.length();
    String res = "";
    boolean[][] dp = new boolean[n][n];

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i 代表长度减去 1

            if (dp[i][j] &&  j - i + 1 > res.length()) {
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}
```

#### Space Optimized DP - Time O(n^2), space O(n)

```java
public String longestPalindrome7(String s) {
        int n = s.length();
        String res = "";
        boolean[] P = new boolean[n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
                if (P[j] && j - i + 1 > res.length()) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }
```

#### Expand Around Center - Time O(n^2) Space O(1)

```java
public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
            if (s == null || s.length() <= 1) {
                return s;
            }

            String longest = s.substring(0, 1);
            for (int i = 0; i < s.length(); i++) {
                // get longest palindrome with center of i
                String tmp = helper(s, i, i);
                if (tmp.length() > longest.length()) {
                    longest = tmp;
                }

                // get longest palindrome with center of i, i+1
                tmp = helper(s, i, i + 1);
                if (tmp.length() > longest.length()) {
                    longest = tmp;
                }
            }

            return longest;
    }

    // Given a center, either one letter or two letter,
    // Find longest palindrome
    public String helper(String s, int begin, int end) {
        while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
        return s.substring(begin + 1, end);
    }
}
```

#### Another expand-center implementation

```java
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        String longest = "";

        for (int i = 0; i < s.length(); i++) {
            // single center
            String tmp = helper(s, i, i);
            if (tmp.length() > longest.length()) {
                longest = tmp;
            }

            // dual center
            tmp = helper(s, i, i + 1);
            if (tmp.length() > longest.length()) {
                longest = tmp;
            }

        }
        return longest;
    }

    // center expand helper function
    // @return longest string centered at i, j
    private String helper(String s, int i, int j) {
         if (i >= s.length() || j >= s.length()) {
             return "";
         }
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        return s.substring(i + 1, j);
    }
}
```

#### Expand Center - O(n^2) time, O(1) space

@jinwu

7 ms, faster than 99.69%

```java
public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2)
        return s;

    for (int i = 0; i < len-1; i++) {
         extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
         extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxLen < k - j - 1) {
        lo = j + 1;
        maxLen = k - j - 1;
    }
}}
```

## Reference

* [LeetCode Discussion](https://discuss.leetcode.com/topic/21848/ac-relatively-short-and-very-clear-java-solution)
* [\*programcreek: Longest Palindromic Substring (Java)](http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/)
* [水中的鱼: Longest Palindromic Substring 解题报告](http://fisherlei.blogspot.com/2012/12/leetcode-longest-palindromic-substring.html)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/longest_palindromic_substring.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.