Minimum Appends for Palindrome!

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

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