Problems that work from both ends

Palindrome questions differ by one word and by an entire solution, so reading the question carefully is most of the work.

Substring: contiguous

table[i][j] is a boolean: is the stretch from i to j a palindrome?

def longest_palindromic_substring(s):
    n = len(s)
    ok = [[False] * n for _ in range(n)]
    start = length = 1
    for i in range(n): ok[i][i] = True
    for i in range(n - 1):
        if s[i] == s[i+1]:
            ok[i][i+1] = True
            start, length = i, 2
    for size in range(3, n + 1):             # by increasing length
        for i in range(n - size + 1):
            j = i + size - 1
            if s[i] == s[j] and ok[i+1][j-1]:
                ok[i][j] = True
                start, length = i, size
    return s[start:start + length]

A boolean is enough because being contiguous leaves no freedom: the stretch either is a palindrome or it is not, with nothing to optimise inside it.

Subsequence: characters may be skipped

table[i][j] is a length.

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n): dp[i][i] = 1
    for size in range(2, n + 1):
        for i in range(n - size + 1):
            j = i + size - 1
            if s[i] == s[j]:
                dp[i][j] = 2 + (dp[i+1][j-1] if size > 2 else 0)
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

Here every range has a best value rather than a verdict, because the middle can be discarded.

The simpler solution for substrings

Expand around each centre, which needs no table:

def expand(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1; right += 1
    return s[left+1:right]

2n - 1 centres, each expanding at most n, so O(n^2) time and O(1) space. Better than the table on both counts, and a good reminder that dynamic programming being applicable does not make it the best tool.

Manacher's algorithm does it in O(n) and is rarely expected.

The trap

The longest palindromic subsequence equals the longest common subsequence of the string and its reverse. That identity is true and useful.

The same trick does not work for substrings. The longest common substring of a string and its reverse can be a stretch that is not a palindrome, and it is a classic wrong answer.