5. 最长回文子串

/*
    观察数据范围1000，所以可用n^2的做法
    以每一个点作为中心点，分别向两边扩展，情况有两种：回文串是奇数或者偶数
*/

class Solution {
public:
    string longestPalindrome(string s) {
        int len = 0;
        string ans;
        for(int k=0; k <s.size();k ++)
        {
            // 1. 回文串是偶数
            int i = k, j = k + 1;
            while(i >= 0 && j < s.size() && s[i] == s[j]) i--, j ++;
            if(j - i - 1 > len) // 这里是 -1 不是 + 1
            {
                len = j - i - 1;
                ans = s.substr(i + 1,len);
            }

            // 2. 回文串是奇数
            i = k - 1, j = k + 1;
            while(i >= 0 && j < s.size() && s[i] == s[j]) i--, j ++;
            if(j - i - 1 > len)
            {
                len = j - i - 1;
                ans = s.substr(i + 1,len);
            }

        }

        return ans;
    }
};

647. 回文子串

class Solution {
public:
    int countSubstrings(string s) {
        // 中心扩展法，每个点都可以作为中心,时间复杂度O(n ^ 2),空间O(1)
        int n = s.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            int l = i, r = i; //以单字母为中心
            while (l >= 0 && r < n && s[l--] == s[r++]) ++ans;
            l = i, r = i + 1; //以双字母为中心
            while (l >= 0 && r < n && s[l--] == s[r++]) ++ans;
        }
        return ans;
    }
};

516. 最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        /*
            f[i,j]: 区间[i,j]的最长回文子序列的长度

            f[i][j] = f[i + 1][j - 1] + 2, s[i] == s[j];
            f[i][j] = max(f[i + 1][j],f[i][j - 1]);
            初始化：f[i][i] = 1;
            答案： ans = f[0][n - 1]
        */

        int n = s.size();
        vector<vector<int>> f(n,vector<int>(n));

        for(int i = n - 1; i >= 0;i -- ) // 要用到i+1层，所以i从大到小
        {
            f[i][i] = 1;
            for(int j = i + 1;j < n;j ++ )
            {
                if(s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;
                else f[i][j] = max(f[i+1][j],f[i][j - 1]);
            }
        }

        return f[0][n - 1];
    }
};

125. 验证回文串

class Solution {
public:
    bool isPalindrome(string s) {
        // 双指针判定回文串，从边沿开始，时间复杂度O(n),空间O(1);
        int i = 0, j = s.size() - 1;

        for(int i = 0;i < s.size();i ++ )
            if(s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a'; // 大写转小写

        while(i < j)
        {
            while(i < j && !check(s[i])) i ++ ;
            while(i < j && !check(s[j])) j -- ;
            if(s[i] != s[j]) return false;
            i ++ ,j -- ;
        }
        return true;
    }

    bool check(char c) // 检查是否是小写字母或者数字
    {
        if(c >= 'a' && c <= 'z' || c >= '0' && c <= '9') return true;
        return false;
    }
};

409. 最长回文串

class Solution {
public:
    int longestPalindrome(string s) {
        /*
            最长包括偶数次和至多一个奇数次
            把偶数次的字符加起来，奇数次-1就变成偶数次

        */
        unordered_map<char,int> cnt;
        for(auto c : s) cnt[c] ++;

        int res = 0;
        for(auto [k,v] : cnt)
        {
            if(v % 2 == 0) res += v;
            else res += v - 1;
        }
        if(res != s.size()) res ++; // 可再添多一个单字符
        return res;
    }
};