G: Palindromic Naming

https://open.kattis.com/problems/palindromic

  • Firstly, notice that the problem is essentially asking for the number of subsequences of the original string that are palindromes. As there are exponentially many subsequences, generating all possible subsequences and checking if it is a palindrome is too slow!

  • You can use dynamic programming to solve this problem :)

  • Let dp[i][j]dp[i][j] denote the number of palindromic subsequences of the substring sisi+1...sjs_is_{i+1}...s_j.

  • Firstly, dp[i][i]=1dp[i][i]=1 for all positions ii as any string of length 11 is a palindrome. Further, dp[i][i+1]=3dp[i][i+1]=3 if si=si+1s_i=s_{i+1} as sis_i, si+1s_{i+1}, and sisi+1s_is_{i+1} are all palindromes. Otherwise, dp[i][i+1]=2dp[i][i+1]=2 as only sis_i and si+1s_{i+1}are palindromes.

  • We iterate in increasing order of widths w. In other words, we first considering all palindromic subsequences at most 2 characters apart, then at most 3 characters apart and so on.

  • Now, our transitions:

    1. If sisjs_i \neq s_j, we cannot create any new palindromes using the characters at positions ii and jj. Thus, by inclusion-exclusion, dp[i][j]=dp[i][j1]+dp[i+1][j]dp[i+1][j1]dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1].

    2. If , si=sjs_i = s_j​, for every palindrome in si+1...sj1s_{i+1}...s_{j-1}, we can add sis_iand sjs_jto create a new palindrome sisi+1...sj1sjs_is_{i+1}...s_{j-1}s_j​. Furthermore, sisjs_is_j​is also a palindrome. So, we have dp[i+1][j1]+1dp[i+1][j-1]+1 new palindromes in addition to the ones we already had. So, in this case, dp[i][j]=dp[i][j1]+dp[i+1][j]+1dp[i][j]=dp[i][j-1]+dp[i+1][j]+1.

  • The required answer is dp[1][n]dp[1][n].

Last updated