G: Palindromic Naming

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

Last updated 3 years ago

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]$ denote the number of palindromic subsequences of the substring $s_is_{i+1}...s_j$ .

Note that the empty string is not considered a palindrome.

Firstly, $dp[i][i]=1$ for all positions $i$ as any string of length $1$ is a palindrome. Further, $dp[i][i+1]=3$ if $s_i=s_{i+1}$ as $s_i$ , $s_{i+1}$ , and $s_is_{i+1}$ are all palindromes. Otherwise, $dp[i][i+1]=2$ as only $s_i$ and $s_{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 $s_i \neq s_j$ , we cannot create any new palindromes using the characters at positions $i$ and $j$ . Thus, by, $dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]$ .
2. If , $s_i = s_j$ , for every palindrome in $s_{i+1}...s_{j-1}$ , we can add $s_i$ and $s_j$ to create a new palindrome $s_is_{i+1}...s_{j-1}s_j$ . Furthermore, $s_is_j$ is also a palindrome. So, we have $dp[i+1][j-1]+1$ new palindromes in addition to the ones we already had. So, in this case, $dp[i][j]=dp[i][j-1]+dp[i+1][j]+1$ .
The required answer is $dp[1][n]$ .

Remember to perform all calculations modulo 1 000 000 007.

Last updated 3 years ago

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]$ denote the number of palindromic subsequences of the substring $s_is_{i+1}...s_j$ .

Note that the empty string is not considered a palindrome.

Firstly, $dp[i][i]=1$ for all positions $i$ as any string of length $1$ is a palindrome. Further, $dp[i][i+1]=3$ if $s_i=s_{i+1}$ as $s_i$ , $s_{i+1}$ , and $s_is_{i+1}$ are all palindromes. Otherwise, $dp[i][i+1]=2$ as only $s_i$ and $s_{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 $s_i \neq s_j$ , we cannot create any new palindromes using the characters at positions $i$ and $j$ . Thus, by, $dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]$ .
2. If , $s_i = s_j$ , for every palindrome in $s_{i+1}...s_{j-1}$ , we can add $s_i$ and $s_j$ to create a new palindrome $s_is_{i+1}...s_{j-1}s_j$ . Furthermore, $s_is_j$ is also a palindrome. So, we have $dp[i+1][j-1]+1$ new palindromes in addition to the ones we already had. So, in this case, $dp[i][j]=dp[i][j-1]+dp[i+1][j]+1$ .
The required answer is $dp[1][n]$ .

Remember to perform all calculations modulo 1 000 000 007.