https://leetcode.com/problems/longest-palindromic-substring/

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

Input: "babad"  
Output: "bab" // "aba" also fine

idea:

1. populate all possible substrings C(n+1, 2)
   1. convert string to new one with insert position '_' ( "_b_a_b_a_d" ), 所以对每个string 我们都有n + 1 个可插入位置，任意取两个位置(L, R) ， 在他们之间包含的字母就是可生成substring. 即从n + 1个中选2个
2. palindromic string ( palindrome is a word or phrase that reads the same backward as forward )

所以simple idea 是check all possible substring to see whether it is a palindrome. n^2 for creat substrings * O(n) for check

improve:

我们判断回文可以判断首尾字母是否一样 然后remove 首尾继续 直到 string 为空

palindromic string S = [C1,C2,...Cn-1,Cn] ==> if S is palindrome, subS = [C2,...Cn-1] should also be a palindrome

这是一个优化的切入点，即加入这个String S是回文，除去首尾也必然是回文的。当然对于length < 3的string我们稍微处理一下就好了

所以我们假如对于一个string 可以知道他之前的substring (length = s.length() - 2) 是否是substring

substring(C1,.., Cn-1) is palindrome && C1 == C2 ==> string S(C1,..,Cn) 也是palindrome

所以为了不重复计算， 保留之前的substring 信息 我们可以用一个array 来标记 substring是否回文

在之后长一点的string 判断的时候就直接利用 => O(n^2) space + length from 1 to N

“因为每次只用到比当前小2长度的substring， 因此数组可以优化到3N” // 滚动数组， DP常见空间优化

code sample:

public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int n = s.length();
        boolean[][] isP = new boolean[3][n];

        String res = "";
        for (int len = 1; len <= n; ++len) {
            for (int i = 0; i + len <= n; ++i) {
                char c1 = s.charAt(i);
                int j = i + len - 1;
                char c2 = s.charAt(j);
                if (c1 == c2 && (len < 3 || isP[(len-2)%3][i+1])) {
                    isP[len%3][i] = true;
                    if (len > res.length()) {
                        res = s.substring(i, i + len);
                    }
                } else {
                    isP[len%3][i] = false; // this is important, otherwise it might be a dirty data from short subtring
                }
            }
        }
        return res;
    }

继续优化空间

因为我们只要求最大， 我们就可以从每一个可能最小substring 出发不断expand，直到invalid (not palindrome or array overflow)

base case 都是从 len = 0 和 1 开始的

Conclusion: 优化思路就是在计算某一个状态时候，利用一下之前已经计算过的子状态而不再需要重复计算直到base case