Dhanadeepa_Red's blog

By Dhanadeepa_Red, history, 4 months ago, In English,

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

Tags #dp
 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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]