Minimum Characters required to make a String Palindromic

• Time : $O(n)$
• Space : $O(n)$

int Solution::solve(string A) {
    string s = "#";
    for(auto ch : A) {
        s.push_back(ch);
        s.push_back('#');
    }
    vector<int> dp(s.size());
    int ma = 0;
    for(int i = 0, l = 0, r = -1; i < s.size(); i++) {
        dp[i] = max(0, min(r - i, r + l - i >= 0 ? dp[r + l - i] : -1));
        while(i + dp[i] < s.size() and i - dp[i] >= 0 and s[i + dp[i]] == s[i - dp[i]]) dp[i]++;
        if(r < i + dp[i]) {
            r = i + dp[i];
            l = i - dp[i];
        }
        if(i - dp[i] == -1) ma = i + dp[i];
    }
    int res = 0;
    for(int i = ma; i < s.size(); i++) res += s[i] != '#';
    return res;
}