algo-aha

最长回文串

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

int countSubstrings(string s) {
    // 设dp[i][j]表示s[i..j]是否是回文串，0<=i<=j<N
    // dp[i][j] = s[i]==s[j] && dp[i+1][j-1]
    // dp在i维上只依赖i+1项，可省掉i维，i仍从右往左遍历
    // 要让dp[j-1]表示旧状态dp[i+1][j-1]，j从右往左遍历
    const int N = s.size();
    vector<bool> dp(N, false);
    int ans = 0;
    for (int i = N - 1; i >= 0; i--) {
        for (int j = N - 1; j >= i; j--) {
            dp[j] = (s[i] == s[j]);
            if (i + 1 <= j - 1) dp[j] = dp[j] && dp[j-1];

            if (dp[j]) ans++;
        }
    }
    return ans;
}

找回文串还可以从各可能的中心往外扩展。

string longestPalindrome(string s) {
    int longest = 0, lo = 0;
    for (int i = 0; i < s.size(); i++) {
        int len1 = expand(s, i, i);
        int len2 = expand(s, i, i + 1);
        int len = max(len1, len2);
        if (len > longest) {
            longest = len;
            lo = i - (len - 1) / 2;
        }
    }
    return s.substr(lo, longest);
}

int expand(const string &s, int l, int r) {
    while (l >= 0 && r < s.size() && s[l] == s[r]) {
        l--;
        r++;
    }
    return r - l - 1; // (l,r)
}

去找S和S'（\(S_{reversed}\)）的最长公共子串是错的。比如S=abacdfgdcaba、S'=abacdgfdcaba，其最长公共子串abacd并不是回文。

做最少的切割，使变成一个个回文串

• https://leetcode.com/problems/palindrome-partitioning-ii/

回文子串的判断同上dp

int minCut(string s) {
    // 设dp[i][j]表示s[i..j]是回文串，0<=i<=j<N
    // dp[i][j] = s[i]==s[j] && dp[i+1][j-1]
    const int N = s.size();
    vector<vector<bool>> dp(N, vector<bool>(N, false));
    for (int i = N - 1; i >= 0; i--) {
        for (int j = i; j < N; j++) {
            dp[i][j] = s[i] == s[j];
            if (i + 1 <= j - 1) dp[i][j] = dp[i][j] && dp[i+1][j-1];
        }
    }

    // 设cut[i]表示子串s[0..i]的最少切割数，0<=i<N
    // dp[0][i]==true时，cut[i]=0；否则，对于0<=k<i，
    // 若满足dp[k+1][i]==true，cut[i]=min{ cut[k]+1 }
    vector<int> cut(N, INT_MAX);
    for (int i = 0; i < N; i++) {
        if (dp[0][i]) {
            cut[i] = 0;
        } else {
            for (int k = 0; k < i; k++) {
                if (dp[k+1][i]) {
                    cut[i] = min(cut[i], cut[k] + 1);
                }
            }
        }
    }
    return cut[N-1];
}

最长回文子序列

• https://leetcode.com/problems/longest-palindromic-subsequence/

int longestPalindromeSubseq(string s) {
    // 设dp[i][j]表示s[i..j]的最长回文子序列长，0<=i<=j<N
    // 若s[i]==s[j]，dp[i][j]=dp[i+1][j-1]+2，i<j
    // 否则，dp[i][j]=max(dp[i+1][j], dp[i][j-1])
    // 初始dp[i][i]=1
    const int N = s.size();
    vector<vector<int>> dp(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        dp[i][i] = 1;
    }

    for (int len = 2; len <= N; len++) {
        for (int i = 0; i + len <= N; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][N-1];
}

不同回文子序列的个数

• https://leetcode.com/problems/count-different-palindromic-subsequences/

“不同”子序列，按字母划分子问题

class Solution {
    const int CHAR_CNT = 4; // 只有abcd四种字母
    const int MOD = 1e9 + 7;
public:
    int countPalindromicSubsequences(string S) {
        // 考虑某字母作最外层的区间，比如"bccb"，b作最外层的区间S[firstIdx(b)..lastIdx(b)]。
        // 这最外层可贡献回文b（不再考虑内层）、bb（firstIdx(b)!=lastIdx(b)）。
        // 当最外层为bb时，内层可为空集和非空子问题S[firstIdx(b)+1..lastIdx(b)-1]]。
        // 只要最外层不同就一定是不同的回文串，不用管内层是什么，计数可累加。
        const int N = S.size();
        vector<set<int>> idxSets(CHAR_CNT); // char=>idxSet
        for (int i = 0; i < N; i++) {
            idxSets[S[i] - 'a'].insert(i);
        }

        vector<vector<int>> memo(N, vector<int>(N, -1)); // S[lo..hi] => count
        return dfs(0, N - 1, idxSets, memo);
    }
    
    int dfs(int lo, int hi, vector<set<int>> &idxSets, vector<vector<int>> &memo) {
        if (lo > hi) return 0;
        if (memo[lo][hi] != -1) return memo[lo][hi];
        
        long ans = 0;
        for (int i = 0; i < CHAR_CNT; i++) {
            auto itLo = idxSets[i].lower_bound(lo);
            if (itLo == idxSets[i].end() || *itLo > hi) continue;
            auto itHi = idxSets[i].upper_bound(hi); 
            itHi--; // *itLo<=hi，<=hi非空，可itHi--
            ans += (*itLo == *itHi) ? 1 : 2; // 相等时贡献c，不等时贡献c和cc
            ans += dfs(*itLo + 1, *itHi - 1, idxSets, memo); // 剥掉最外层、内层子问题
        }
        memo[lo][hi] = ans % MOD;
        return memo[lo][hi];
    }
};

扩展：不同子序列的个数，都是按字母作某种划分