Palindrome & DP

Summary

In this post, I will introduce some problems related to palindrome and dynamic programming.

A palindrome has a property that, if we add two equal characters in both side of it, it is still a palindrome.

OJ

	Trick	Difficulty
LC 1278. Palindrome Partitioning III	Cost to Make Palindrome + DP	6-7 points
LC 132. Palindrome Partitioning II	Is Palindrome + DP	5 points
LC 730. Count Different Palindromic Subsequences	3D DP	7 points
LC 1246. Palindrome Removal	DP + "A...A" is still a Palindrome	6-7 points

Details

LC 1278 Palindrome Partitioning III

Difficulty: 6-7 points

Given a string s containing lowercase letters and an integer k. You could,

• First, change some characters of s to other lowercase English letters.
• Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

A naive interval solution

// O(n^3k)
alg[i][j][k] = min{ alg[i][l][1] + alg[l + 1][j][k - 1], for l in [i, j - 1]}
    
alg[i][j][1] = alg[i + 1][j - 1][1] + s[i] != s[j]

A better solution

// O(n^2k)
alg[i][k] = {alg[j + 1][k - 1] + make_palindrome(s[i:j]), for j in [i, n - 2]}

alg[i][1] = make_palindrome(s[i:n])

make_palindrome[i][j] = make_palindrome[i + 1][j - 1] + (s[i] != s[j])

LC 730. Count Different Palindromic Subsequences

Difficulty: 7 points

Given a string s, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7. Each character s[i] will be in the set {'a', 'b', 'c', 'd'}.

The problem is difficult since the subsequences need to be unique. We define alg[i][j][k] so that it counts the different palindromic subsequences among s[i,...,j] and we expect s[i] and s[j] to be 'a' + c.

alg[i][j][c]
  1. if s[i] == 'a' + c && s[j] == 'a' + c: 2 + alg[i + 1][j - 1][0,1,2,3] ('a' + 'aa' + 'a, ... ,a')
  2. else if s[i] != 'a' + c: alg[i + 1][j][k]
  3. else if s[j] != 'a' + c: alg[i][j - 1][k]
  4. else: alg[i + 1][j - 1][k] 
    
// alg[i][i][c] = s[i] == 'a' + c
// alg[i][i + 1][c] = 
    //  1. if s[i] == 'a' + c && s[i + 1] == 'a' + c: 2
    //  2. else if s[i] == 'a' + c: 1
    //  3. else if s[i + 1] == 'a' + c: 1
    //  4. else: 0

LC 1246. Palindrome Removal

Difficulty: 6-7 points

Given an integer array arr, in one move you can select a palindromic subarray arr[i], arr[i+1], ..., arr[j] where i <= j, and remove that subarray from the given array. Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal. Return the minimum number of moves needed to remove all numbers from the array.

The first glance might make one feel like it is a dynamic & interval DP problem. However, the thought of dynamic is too complex. Think in this way, if arr[i] == arr[j], we know the problem alg[i][j] is the same as alg[i + 1][j - 1], since any subarray in range arr[i+1, j-1] could be a new subarray by adding one characters in both sides without any cost. If arr[i]!=arr[j], we could delete a single character, or find a arr[k] to make arr[k]==arr[i] or arr[k]==arr[j]. These are the two only ways for arr[i] or arr[j], since it must be deleted alone or in a subarray.

alg[i][j] = 
  1. if arr[i] == arr[j]:
       alg[i + 1][j - 1]
  2. alg[i][k] + alg[k + 1][j] if arr[i] == arr[k] || arr[k + 1] == arr[j] for k in [i + 1, ... , j - 1]
  3. 1 + alg[i + 1][j]
  4. 1 + alg[i][j - 1]