valid-palindrome-iii.cpp

// Time:  O(n^2)
// Space: O(n)

class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        if (s == string(s.rbegin(), s.rend())) {  // optional, to optimize special case
            return true;
        }
        
        vector<vector<int>> dp(2, vector<int>(s.size(), 1));
        for (int i = s.length() - 2; i >= 0; --i) {
            for (int j = i + 1; j < s.length(); ++j) {
                if (s[i] == s[j]) {
                    dp[i % 2][j] = (i + 1 <= j - 1) ? 2 + dp[(i + 1) % 2][j - 1] : 2;
                } else {
                    dp[i % 2][j] = max(dp[(i + 1) % 2][j], dp[i % 2][j - 1]);
                }
            }
        }
        return s.length() <= k +dp[0][s.length() - 1];
    }
};