Palindrome

Palindromes are a very common type of problem in programming interviews, as well as competitive programming.

You can actually reverse a palindrome mathematically:

int reverse(int n)
{
    int r=0;
    while(n>0)
    {
        r=r*10+n%10;
        n/=10;
    }
    return r;
}

I tend to struggle with Palindrome problems. Going to include some template code to solve these problems:

• Longest Palindromic Subsequence
• Longest Palindromic Substring

Longest Palindromic Substring

I actually could not come up with a solution.

Longest Palindromic Sequence

From MIT 6.046: https://www.youtube.com/watch?v=Tw1k46ywN6E&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=14&ab_channel=MITOpenCourseWare - 16:20

My solution on Leetcode

int dp[1000][1000];
int longestDP(int l, int r, string &s) {
    if (l > r) return 0;
    if (l == r) return 1;
    if (dp[l][r] != 0) {
        return dp[l][r];
    }
    if (s[l] == s[r]) {
        return dp[l][r] = 2 + longestDP(l+1, r-1, s);
    } else {
        return dp[l][r] = max(longestDP(l+1, r, s), longestDP(l, r-1, s));
    }
}
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        memset(dp, 0, sizeof(dp));
        return longestDP(0, s.length()-1, s);
    }
};

Concepts

• Manacher’s Algorithm