forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
GFG_CountPalindromicSubsequences.cpp
55 lines (47 loc) · 1.53 KB
/
GFG_CountPalindromicSubsequences.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
https://practice.geeksforgeeks.org/problems/count-palindromic-subsequences/1
Count Palindromic Subsequences
*/
class Solution{
public:
const int mod = 1e9+7;
vector<vector<long long int>> memo;
string s;
/*You are required to complete below method */
long long int countPS(string str)
{
int n = str.length();
// s = str;
// memo.resize(n+1, vector<long long int>(n+1, -1));
// return solve( 0, n-1);
vector<vector<long long int>> dp(n, vector<long long int>(n, 0));
for(int i=0; i<n; i++)
dp[i][i] = 1;
for(int k=2; k<=n; k++)
{
for(int i=0; i<n-k+1; ++i)
{
int j = i+k-1;
if(str[i]==str[j])
dp[i][j] = (dp[i+1][j]+dp[i][j-1] + 1)%mod;
else
dp[i][j] = (dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1])%mod;
if(dp[i][j]<0) dp[i][j] += mod;
}
}
return dp[0][n-1];
}
long long int solve(int i, int j)
{
if(i>j) return 0;
if(i==j) // palindrome of length 1
return 1;
if(memo[i][j] != -1) return memo[i][j];
if(s[i]==s[j]) // if first and last char are same
memo[i][j] = (1+solve( i+1, j) + solve( i, j-1))%mod;
else
memo[i][j] = (solve( i+1, j) + solve( i, j-1) - solve(i+1, j-1))%mod;
if(memo[i][j]<0) memo[i][j] += mod;
return memo[i][j];
}
};