LeetCode 2484: Count Palindromic Subsequences
Problem Description
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)
Solutions
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];
}
}Loading editor...