1. Introduction

A palindromic subsequence is a sequence of characters in a string that:

1. Reads the same forwards and backwards.
2. Does not need to be contiguous (unlike a substring).

Example:

String: "bbabcbcab"
Longest palindromic subsequence: "babcbab" (length 7)

Typical Problems:

• Find the length of the longest palindromic subsequence (LPS).
• Count the number of palindromic subsequences.
• Minimum deletions to make a string a palindrome.
• Minimum insertions to make a string a palindrome.

This pattern is a classic Dynamic Programming (DP) problem because the solution depends on substrings and overlapping subproblems.

---

2. When to Use Palindromic Subsequence Pattern

Use this pattern when:

1. The problem involves palindromes in strings.
2. You need to maximize or minimize a property (length, count, deletions).
3. Substrings/subsequences overlap, indicating a DP solution.
4. You see recursive choices based on matching or mismatching characters at two ends.

Problem Indicators:

• “Find longest palindromic subsequence”
• “Make string a palindrome with minimum deletions/insertions”
• “Count palindromic subsequences”

---

3. Core Idea

For a string s[i..j], consider the two ends of the substring:

1. If s[i] == s[j] → these characters can be part of a palindromic subsequence. LPS(i, j) = 2 + LPS(i+1, j-1) (The +2 accounts for matching characters at the ends)
2. If s[i] != s[j] → one of the ends must be excluded: LPS(i, j) = max(LPS(i+1, j), LPS(i, j-1))

Base Case:

• Single character: LPS(i, i) = 1
• Empty substring: LPS(i, j) = 0 if i > j

This forms the recursive DP relation.

---

4. Recursive Approach (Exponential Time)

public int longestPalindromeSubseq(String s) {
    return helper(s, 0, s.length() - 1);
}

private int helper(String s, int i, int j) {
    if (i > j) return 0;
    if (i == j) return 1;

    if (s.charAt(i) == s.charAt(j)) {
        return 2 + helper(s, i + 1, j - 1);
    } else {
        return Math.max(helper(s, i + 1, j), helper(s, i, j - 1));
    }
}

• Time Complexity: O(2^n)
• Space Complexity: O(n) recursion stack

---

5. Top-Down DP (Memoization)

public int longestPalindromeSubseqMemo(String s) {
    int n = s.length();
    int[][] memo = new int[n][n];
    for (int[] row : memo) Arrays.fill(row, -1);
    return helper(s, 0, n - 1, memo);
}

private int helper(String s, int i, int j, int[][] memo) {
    if (i > j) return 0;
    if (i == j) return 1;
    if (memo[i][j] != -1) return memo[i][j];

    if (s.charAt(i) == s.charAt(j)) {
        memo[i][j] = 2 + helper(s, i + 1, j - 1, memo);
    } else {
        memo[i][j] = Math.max(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo));
    }
    return memo[i][j];
}

• Time Complexity: O(n²)
• Space Complexity: O(n²) + recursion stack

---

6. Bottom-Up DP (Tabulation)

public int longestPalindromeSubseqDP(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;  // Base case: single character

        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = 2 + dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

• Time Complexity: O(n²)
• Space Complexity: O(n²)

---

7. Space-Optimized DP

Since dp[i][j] depends only on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1], it can be optimized to O(n) with careful iteration (optional for advanced use).

---

8. Variants and Related Problems

1. Minimum Deletions to Make String a Palindrome

minDeletions = n - LPS(s)

2. Minimum Insertions to Make String a Palindrome

minInsertions = n - LPS(s)

3. Count All Palindromic Subsequences

• Use DP with recurrence considering single character and pairs to count distinct palindromes.

4. Longest Palindromic Substring vs Subsequence

• Substring requires contiguous characters, subsequence can skip characters.

---

9. When to Use This Pattern

• When problems involve palindromes and subsequences.
• When decisions are based on first and last characters.
• When the problem can be broken into smaller substrings.
• When you see maximize/minimize operations with overlapping subproblems.

Indicators:

• “Longest palindromic subsequence”
• “Make string a palindrome with minimum operations”
• “Count palindromic subsequences”

---

10. Key Takeaways

1. Pattern Recognition: Recurrence based on first and last character matches.
2. Base Cases: Single character → 1, empty substring → 0.
3. DP Relation: if s[i] == s[j] → dp[i][j] = 2 + dp[i+1][j-1] else → dp[i][j] = max(dp[i+1][j], dp[i][j-1])
4. Approaches:
   • Recursion → O(2^n)
   • Top-Down DP (Memoization) → O(n²)
   • Bottom-Up DP (Tabulation) → O(n²)
   • Space-optimized → O(n)
5. Many palindrome-related problems can be solved using this pattern, including minimum insertions/deletions, counting, and subsequence variations.