Palindrome Removal

Problem

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.

Examples

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

Solution

Method 1 – Dynamic Programming on Intervals

Intuition

We want to remove the array in the minimum number of moves, where each move removes a palindromic subarray. If the ends of a subarray are equal, we can try to remove them together, possibly reducing the number of moves. This suggests a DP approach on intervals.

Approach

1. Let dp[i][j] be the minimum moves to remove arr[i..j].
2. Base case: dp[i][i] = 1 (a single element is a palindrome).
3. For i < j, try:
   • Remove arr[i] alone: dp[i][j] = 1 + dp[i+1][j].
   • If arr[i] == arr[j], try removing both ends together: dp[i][j] = min(dp[i][j], dp[i+1][j-1]).
   • For all k in (i, j), if arr[i] == arr[k], try splitting at k: dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]).
4. Fill the DP table for all intervals.
5. The answer is dp[0][n-1].

Code

C++

class Solution {
public:
    int minimumMoves(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(n, n));
        for (int i = 0; i < n; ++i) dp[i][i] = 1;
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                if (arr[i] == arr[j])
                    dp[i][j] = (len == 2) ? 1 : dp[i+1][j-1];
                for (int k = i; k < j; ++k)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
        return dp[0][n-1];
    }
};

Go

func minimumMoves(arr []int) int {
    n := len(arr)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            if i == j {
                dp[i][j] = 1
            } else {
                dp[i][j] = n
            }
        }
    }
    for l := 2; l <= n; l++ {
        for i := 0; i+l-1 < n; i++ {
            j := i + l - 1
            if arr[i] == arr[j] {
                if l == 2 {
                    dp[i][j] = 1
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
            }
            for k := i; k < j; k++ {
                if dp[i][j] > dp[i][k]+dp[k+1][j] {
                    dp[i][j] = dp[i][k]+dp[k+1][j]
                }
            }
        }
    }
    return dp[0][n-1]
}

Java

class Solution {
    public int minimumMoves(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(dp[i], n);
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (arr[i] == arr[j])
                    dp[i][j] = (len == 2) ? 1 : dp[i+1][j-1];
                for (int k = i; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
        return dp[0][n-1];
    }
}

Kotlin

class Solution {
    fun minimumMoves(arr: IntArray): Int {
        val n = arr.size
        val dp = Array(n) { IntArray(n) { n } }
        for (i in 0 until n) dp[i][i] = 1
        for (len in 2..n) {
            for (i in 0..n-len) {
                val j = i+len-1
                if (arr[i] == arr[j])
                    dp[i][j] = if (len == 2) 1 else dp[i+1][j-1]
                for (k in i until j)
                    dp[i][j] = minOf(dp[i][j], dp[i][k] + dp[k+1][j])
            }
        }
        return dp[0][n-1]
    }
}

Python

class Solution:
    def minimumMoves(self, arr: list[int]) -> int:
        n = len(arr)
        dp = [[n] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for l in range(2, n+1):
            for i in range(n-l+1):
                j = i+l-1
                if arr[i] == arr[j]:
                    dp[i][j] = 1 if l == 2 else dp[i+1][j-1]
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
        return dp[0][n-1]

Rust

impl Solution {
    pub fn minimum_moves(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut dp = vec![vec![n as i32; n]; n];
        for i in 0..n { dp[i][i] = 1; }
        for len in 2..=n {
            for i in 0..=n-len {
                let j = i+len-1;
                if arr[i] == arr[j] {
                    dp[i][j] = if len == 2 { 1 } else { dp[i+1][j-1] };
                }
                for k in i..j {
                    dp[i][j] = dp[i][j].min(dp[i][k] + dp[k+1][j]);
                }
            }
        }
        dp[0][n-1]
    }
}

TypeScript

class Solution {
    minimumMoves(arr: number[]): number {
        const n = arr.length;
        const dp: number[][] = Array.from({length: n}, () => Array(n).fill(n));
        for (let i = 0; i < n; i++) dp[i][i] = 1;
        for (let len = 2; len <= n; len++) {
            for (let i = 0; i + len - 1 < n; i++) {
                const j = i + len - 1;
                if (arr[i] === arr[j])
                    dp[i][j] = len === 2 ? 1 : dp[i+1][j-1];
                for (let k = i; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
        return dp[0][n-1];
    }
}

Complexity

• ⏰ Time complexity: O(n^3), where n is the length of arr. We fill an n x n DP table, and for each interval, we may try all possible splits.
• 🧺 Space complexity: O(n^2), for the DP table.