Palindrome Removal - Solution & Explanation
Problem Statement
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] <= 20
Approach Overview
Problem 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.
Solution
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.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode 1246. Palindrome Removal • Algorithms Casts • 4,454 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Palindrome Removal easy or hard?
Palindrome Removal Python/Java solution
How to solve Palindrome Removal in O(n)?
What is the best approach for Palindrome Removal?
Is Palindrome Removal asked at Google/Amazon/Meta?
What data structure is used in Palindrome Removal?
What is the time complexity of Palindrome Removal?
Ready to solve this problem?
Practice Palindrome Removal with our built-in code editor and test cases.
Practice on FleetCode