647. Palindromic Substrings

---

Problem Statement

Given a string, count how many palindromic substrings it contains. Substrings that start or end at different positions are considered distinct even if they consist of the same characters.

Solution using Dynamic Programming

We define a two‑dimensional Boolean table isPal[i][j] that indicates whether the substring from index i to j (inclusive) is a palindrome. Let n be the length of the string. Process i from n-1 down to 0, and for each i iterate j from i to n-1. When s[i] == s[j]:

• If the substring length is at most 2 (j - i <= 1), it is a palindrome.
• Otherwise, it is a palindrome if the inner part isPal[i+1][j-1] is true.

Each time a palindrome is found we increment the count. The bottom‑up traversal guarantees that isPal[i+1][j-1] is already computed.

int countPalindromicSubstrings(char *str) {
    int n = strlen(str);
    int isPal[n][n];
    int total = 0;
    memset(isPal, 0, sizeof(isPal));

    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            if (str[i] == str[j]) {
                if (j - i <= 1 || isPal[i + 1][j - 1] == 1) {
                    isPal[i][j] = 1;
                    ++total;
                }
            }
        }
    }
    return total;
}

The approach runs in O(n²) time and uses O(n²) extra space.

516. Longest Palindromic Subsequence

---

Problem Statement

Given a string s, return the length of the longest palindromic subsequence. The length of s will not exceed 1000.

Dynamic Programming Approach

Let best[i][j] be the length of the longest palindromic subsequence inside the substring s[i..j]. For a single‑character substring, best[i][i] = 1. We then fill the table by iterating i downward and j upward from i+1:

• If s[i] == s[j], the two characters can extend the palindromic subsequence found inside: best[i][j] = best[i+1][j-1] + 2.
• Otherwise, we take the longer option when skipping one of the ends: best[i][j] = max(best[i+1][j], best[i][j-1]).

The final answer is best[0][n-1].

int max(int a, int b) { return a > b ? a : b; }

int longestPalindromicSubseq(char *str) {
    int n = strlen(str);
    int best[n][n];
    memset(best, 0, sizeof(best));

    for (int i = 0; i < n; ++i)
        best[i][i] = 1;

    for (int i = n - 1; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j) {
            if (str[i] == str[j])
                best[i][j] = best[i + 1][j - 1] + 2;
            else
                best[i][j] = max(best[i + 1][j], best[i][j - 1]);
        }
    }
    return best[0][n - 1];
}

This solution also requires O(n²) time and space.