LeetCode 2484: Count Palindromic Subsequences Solution

Master LeetCode problem 2484 (Count Palindromic Subsequences), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2484. Count Palindromic Subsequences

Hard

String Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will maintain a 2D array to store the number of palindromic subsequences for substrings of different lengths. We will iterate over all possible lengths of substrings from 1 to 5 and for each length, we will iterate over all possible starting indices of substrings in the input string. At each step, we will update the count of palindromic subsequences based on the characters at the current starting index and the current length.

Time complexity: O(n^2) Space complexity: O(n^2)

Solution Code

class Solution {
    public int countPalindromicSubsequences(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        int MOD = 1000000007;

        for (int len = 1; len <= 5; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                if (len == 1) {
                    dp[i][j] = 1;
                } else {
                    if (s.charAt(i) == s.charAt(j)) {
                        int left = i + 1;
                        int right = j - 1;
                        while (left <= right && s.charAt(left) != s.charAt(i)) {
                            left++;
                        }
                        while (left <= right && s.charAt(right) != s.charAt(i)) {
                            right--;
                        }
                        if (left > right) {
                            dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                        } else if (left == right) {
                            dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                        } else {
                            dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
                        }
                    } else {
                        dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
                    }
                }
                dp[i][j] = dp[i][j] < 0 ? dp[i][j] + MOD : dp[i][j] % MOD;
            }
        }

        return dp[0][n - 1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2484 (Count Palindromic Subsequences)?

This page provides optimized solutions for LeetCode problem 2484 (Count Palindromic Subsequences) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2484 (Count Palindromic Subsequences)?

The time complexity for LeetCode 2484 (Count Palindromic Subsequences) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2484 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2484 in Java, C++, or Python.

Back to LeetCode Solutions