3844. 最長的準迴文字字串

思路

每一個字元都可以作為迴文的中心向外擴展，中心也可以是兩個字元。
在擴展時，假如遇到了不同的字元，就使用掉跳過的機會，
而跳過有兩種選擇，不是跳左就是跳右邊，因此兩種情況都要參考進來。

假如在相等時使用跳過，這樣的操作只會浪費掉了機會，並不會讓未來可以延展的更多。

程式碼

中心擴展法

class Solution {
private:
    int getRemain(string& s, int l, int r) {
        int n = s.length();
        while(l >= 0 && r < n && s[l] == s[r]) {
            l--;
            r++;
        }
        return r - l - 1;
    }
    int expand(string& s, int l, int r) {
        int n = s.length();
        while(l >= 0 && r < n && s[l] == s[r]) { // 延展
            l--;
            r++;
        }
        // 遇到不相同
        // 在範圍內，兩種選擇
        if(l >= 0 && r < n) { 
            int len1 = getRemain(s, l - 1, r);
            int len2 = getRemain(s, l, r + 1);
            return max(len1, len2);
        }
        // 有一邊不在範圍內，或兩邊都不在
        int len = r - l - 1;
        if(l >= 0 || r < n) { // 一邊不在，隨意抓取刪掉的字元
            return len + 1;
        }
        // 兩邊都不在
        return len;
    }
public:
    int almostPalindromic(string s) {
        int n = s.length();
        int res = 0;
        for(int i = 0; i < n; i++) {
            res = max(res, expand(s, i, i));
            res = max(res, expand(s, i, i + 1));
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(1)$