Is Palindrome Removal easy or hard?

Palindrome Removal is categorized as a Hard problem because it requires recognizing an interval dynamic programming pattern and designing transitions that merge matching elements across subarrays.

Palindrome Removal Python/Java solution

Most implementations follow the same interval DP recurrence regardless of language. A 2D dp array is filled either with memoized recursion or bottom-up iteration. FleetCode provides complete implementations in Python, Java, C++, Go, and TypeScript.

How to solve Palindrome Removal in O(n)?

An O(n) solution is not known for this problem because each interval can interact with many other positions when forming larger palindromes. The best known solution uses interval dynamic programming with O(n^3) time and O(n^2) memory.

What is the best approach for Palindrome Removal?

The most effective approach is interval dynamic programming. Define dp[i][j] as the minimum moves required to remove the subarray from index i to j. The recurrence tries removing the first element alone or merging it with later matching values to form a larger palindrome. This solution runs in O(n^3) time with O(n^2) space.

Is Palindrome Removal asked at Google/Amazon/Meta?

Palindrome-based dynamic programming problems frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Variants such as palindrome partitioning, minimum removals, and interval DP optimization are common in algorithm interview rounds.

What data structure is used in Palindrome Removal?

The solution primarily uses a 2D dynamic programming table over an array. Each entry dp[i][j] stores the minimum operations needed to remove the subarray between indices i and j.

What is the time complexity of Palindrome Removal?

The optimal interval DP solution runs in O(n^3) time and uses O(n^2) space. The cubic factor comes from evaluating every subarray pair (i, j) and iterating through possible matching positions k within that interval.

Description Hints 3 Solution Video 27:45

1246. Palindrome Removal

Hard46.4% acceptance1 companyPremium elsewhere, free here

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

Asked at 1 company

Microsoft

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

Let dp[i][j] be the solution for the sub-array from index i to index j.

Hint 3

Notice that if we have S[i] == S[j] one transition could be just dp(i + 1, j + 1) because in the last turn we would have a palindrome and we can extend this palindrome from both sides, the other transitions are not too difficult to deduce.

27:45

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2]

Input

[1,3,4,1,5]

Your code is saved on this device.Solution