wish_me's blog

By wish_me, history, 5 years 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

»
5 years 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]

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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]"?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 code
»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
Recursive dp code