### wish_me's blog

By wish_me, history, 5 years ago, Given a string S of length n and a positive integer k. The task is to find number of Palindromic Subsequences of length k.

Examples:

Input : s = "aabab", k = 2

Output : 4

Input : s = "aaa", k = 3

Output : 1

Input: s= "abdbcabda",k=4

Output : 6  Comments (7)
| Write comment?
 » dp[i][j][k] = (s[i] == s[j]) * dp[i + 1][j — 1][k — 1] + dp[i + 1][j][k] + dp[i][j — 1][k] — dp[i + 1][j — 1][k]
•  » » 5 years ago, # ^ | ← Rev. 2 →   thanks a lot.What would be its time complexity O(n*k)?
•  » » » O(n*n*k)
 » Wouldn't it be: "dp[i][j][k] = (s[i] == s[j]) * dp[i + 1][j — 1][k — 2] + dp[i + 1][j][k] + dp[i][j — 1][k] — dp[i + 1][j — 1][k]"?
•  » » 13 months ago, # ^ | ← Rev. 3 →   This is the correct relation imo. Let me explain it further. dp[i][j][k] means the number of palindromic subsequences of size k that occur between i and j (inclusive)So if s[i]==s[j], this would mean that the corner elements are same at the ith and the jth index, so we multiply it with dp[i+1][j-1][k-2] (this means that we exclude ith and jth index and find the number of palindromic subsequences of size k-2 from i+1 to j-1 indices).Again we add dp[i][j-1][k] and dp[i+1][j][k] and subtract dp[i+1][j-1][k] from it which is self explanatory.Number of palindromic subsequences of size 1 between i & j will be j-i+1 ( as all strings of size 1 are palindrome) Number of palindromic subsequences of size 0 between i & j will be 1 Number of palindromic subsequences of size 2 when i+1==j and ith and jth character are equal will be 1 else it will be 0 This is the codeint PalindromicSubsequencesOfSizeK(string s, int KK){ vector>>dp(n+2, vector>(n+2, vector(KK+1,0))); for(int i=n;i>=1;i--){ for(int j=i;j<=n;j++){ dp[i][j]=1; dp[i][j]=j-i+1; if(i+1==j){ if(s[i-1]==s[j-1])dp[i][j]=1; continue; } for(int k=3;k<=KK;k++){ dp[i][j][k]=(s[i-1]==s[j-1])*dp[i+1][j-1][k-2]+dp[i][j-1][k]+dp[i+1][j][k]-dp[i+1][j-1][k]; } } } return dp[n][KK]; } 
•  » » » 11 months ago, # ^ | ← Rev. 2 →   Can you also tell why to subtract dp[i+1][j-1][k] ? Is it because when we fo to i+1,j and i,j-1 we will double count it i+1,j-1 so to cancel it we are subtracting?
•  » » » » Yes