# 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)