Palindromic Substrings

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

c++

int Solution::solve(string A) {
    string s = "#";
    for(auto ch : A) {
        s.push_back(ch);
        s.push_back('#');
    }
    vector<int> dp(s.length());
    int res = 0, l = 0, r = - 1;
    for(int i = 0; i < s.length(); i++) {
        dp[i] = max(0, min(r - i, r + l - i >= 0 ? dp[r + l - i] : -1));
        while(i + dp[i] < s.length() 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];
        }
        res += dp[i] / 2;
    }
    return res;
}