Skip to content

1246. Palindrome Removal πŸ”’

Description

You are 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.

 

Example 1:

Input: arr = [1,2]
Output: 2

Example 2:

Input: arr = [1,3,4,1,5]
Output: 3
Explanation: Remove [4] then remove [1,3,1] then remove [5].

 

Constraints:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 20

Solutions

Solution 1: Dynamic Programming (Interval DP)

Thinking

Each move deletes a palindromic subarray. \(n \le 100\). Optimal substructure on intervals suggests DP: \(f[i][j]\) is the fewest moves to clear \(arr[i..j]\).

Equal ends may vanish with the inner interval; otherwise we split at \(k\) and clear the two sides separately. Filling by interval length makes shorter intervals ready. \(n^3\) is acceptable at \(n=100\).

We define \(f[i][j]\) as the minimum number of operations required to delete all numbers in the index range \([i,..j]\). Initially, \(f[i][i] = 1\), which means that when there is only one number, one deletion operation is needed.

For \(f[i][j]\), if \(i + 1 = j\), i.e., there are only two numbers, if \(arr[i]=arr[j]\), then \(f[i][j] = 1\), otherwise \(f[i][j] = 2\).

For the case of more than two numbers, if \(arr[i]=arr[j]\), then \(f[i][j]\) can be \(f[i + 1][j - 1]\), or we can enumerate \(k\) in the index range \([i,..j-1]\), take the minimum value of \(f[i][k] + f[k + 1][j]\). Assign the minimum value to \(f[i][j]\).

The answer is \(f[0][n - 1]\).

The time complexity is \(O(n^3)\), and the space complexity is \(O(n^2)\). Where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minimumMoves(self, arr: List[int]) -> int:
        n = len(arr)
        f = [[0] * n for _ in range(n)]
        for i in range(n):
            f[i][i] = 1
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if i + 1 == j:
                    f[i][j] = 1 if arr[i] == arr[j] else 2
                else:
                    t = f[i + 1][j - 1] if arr[i] == arr[j] else inf
                    for k in range(i, j):
                        t = min(t, f[i][k] + f[k + 1][j])
                    f[i][j] = t
        return f[0][n - 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minimumMoves(int[] arr) {
        int n = arr.length;
        int[][] f = new int[n][n];
        for (int i = 0; i < n; ++i) {
            f[i][i] = 1;
        }
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (i + 1 == j) {
                    f[i][j] = arr[i] == arr[j] ? 1 : 2;
                } else {
                    int t = arr[i] == arr[j] ? f[i + 1][j - 1] : 1 << 30;
                    for (int k = i; k < j; ++k) {
                        t = Math.min(t, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = t;
                }
            }
        }
        return f[0][n - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minimumMoves(vector<int>& arr) {
        int n = arr.size();
        int f[n][n];
        memset(f, 0, sizeof f);
        for (int i = 0; i < n; ++i) {
            f[i][i] = 1;
        }
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (i + 1 == j) {
                    f[i][j] = arr[i] == arr[j] ? 1 : 2;
                } else {
                    int t = arr[i] == arr[j] ? f[i + 1][j - 1] : 1 << 30;
                    for (int k = i; k < j; ++k) {
                        t = min(t, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = t;
                }
            }
        }
        return f[0][n - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func minimumMoves(arr []int) int {
    n := len(arr)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
        f[i][i] = 1
    }
    for i := n - 2; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            if i+1 == j {
                f[i][j] = 2
                if arr[i] == arr[j] {
                    f[i][j] = 1
                }
            } else {
                t := 1 << 30
                if arr[i] == arr[j] {
                    t = f[i+1][j-1]
                }
                for k := i; k < j; k++ {
                    t = min(t, f[i][k]+f[k+1][j])
                }
                f[i][j] = t
            }
        }
    }
    return f[0][n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function minimumMoves(arr: number[]): number {
    const n = arr.length;
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

    for (let i = 0; i < n; ++i) {
        f[i][i] = 1;
    }

    for (let i = n - 2; i >= 0; --i) {
        for (let j = i + 1; j < n; ++j) {
            if (i + 1 === j) {
                f[i][j] = arr[i] === arr[j] ? 1 : 2;
            } else {
                let t = arr[i] === arr[j] ? f[i + 1][j - 1] : Infinity;
                for (let k = i; k < j; ++k) {
                    t = Math.min(t, f[i][k] + f[k + 1][j]);
                }
                f[i][j] = t;
            }
        }
    }

    return f[0][n - 1];
}

Comments