Watch 6 video solutions for Palindrome Removal, a hard level problem involving Array, Dynamic Programming. This walkthrough by Algorithms Casts has 4,403 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1001 <= arr[i] <= 20Problem Overview: You are given an integer array and can remove any contiguous subarray that forms a palindrome. The goal is to remove the entire array using the minimum number of operations. Each operation deletes one palindromic segment, so the challenge is finding the optimal sequence of removals.
Approach 1: Brute Force Recursion (Exponential Time, O(n!) time, O(n) space)
The straightforward idea is to try removing every possible palindromic subarray and recursively solve the remaining array. For each step, iterate through all subarray boundaries (i, j), check if the segment is a palindrome, remove it, and continue searching for the minimum operations. This approach quickly becomes infeasible because the number of removal orders grows factorially. It’s useful conceptually because it exposes the overlapping subproblems that later motivate dynamic programming.
Approach 2: Top-Down Dynamic Programming (Interval DP) (O(n^3) time, O(n^2) space)
Define dp(l, r) as the minimum moves needed to remove the subarray from index l to r. The base case is a single element, which takes one move. The simplest transition removes arr[l] alone, giving 1 + dp(l+1, r). The key optimization appears when another element matches arr[l]. If arr[l] == arr[k], the two values can become part of the same palindrome after removing the middle segment. That leads to a transition like dp(l+1, k-1) + dp(k+1, r). Memoization stores results for every interval, preventing repeated work. This structure is a classic interval DP problem over an array.
Approach 3: Bottom-Up Interval DP (O(n^3) time, O(n^2) space)
The same recurrence can be implemented iteratively. Create a 2D table dp[i][j] representing the minimum removals for the subarray i..j. Fill the table by increasing subarray length. For each interval, start with removing the first element alone (1 + dp[i+1][j]). Then iterate through all indices k where arr[i] == arr[k]. If the values match, combine the operations so that the two elements disappear in the same palindrome removal, reducing the total operations. This bottom-up order guarantees all smaller intervals are computed before they are needed.
Recommended for interviews: Interviewers typically expect the interval DP solution with O(n^3) time and O(n^2) space. Starting from the brute-force idea shows you understand the problem structure, but recognizing overlapping subproblems and converting them into a memoized or bottom-up DP demonstrates stronger algorithmic reasoning. Interval DP patterns appear frequently in problems involving palindromes, merging segments, or optimal partitioning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(n!) | O(n) | Conceptual understanding of all possible palindrome removals |
| Top-Down Dynamic Programming (Memoized Interval DP) | O(n^3) | O(n^2) | Clear recursive formulation with overlapping subproblems |
| Bottom-Up Interval DP | O(n^3) | O(n^2) | Preferred implementation for interviews and production due to predictable iteration order |