Practice/Yahoo/Leetcode 1246. Palindrome Removal

Leetcode 1246. Palindrome Removal

CodingMust

Problem

You are given an integer array. In each move, you can select any contiguous subarray that forms a palindrome and remove it from the array. After removal, the remaining elements shift together to form a new array.

Your task is to determine the minimum number of moves required to remove all elements from the array.

A palindrome is a sequence that reads the same forward and backward. For example, [1, 2, 1] and [5, 5] are palindromes, while [1, 2, 3] is not.

Requirements

1. Implement a function that takes an integer array as input
2. Return the minimum number of removal operations needed to clear the entire array
3. Each operation removes a contiguous palindromic subarray
4. Elements shift together after each removal

Constraints

• 1 ≤ arr.length ≤ 100
• 1 ≤ arr[i] ≤ 1000
• Time complexity should be reasonable for the given constraints
• Space complexity: O(n²) is acceptable for dynamic programming solutions

Examples

Example 1:

Input: arr = \[1, 2\] Output: 2 Explanation: Remove each element individually since no palindrome spans both elements.

Example 2:

` Input: arr = [1, 3, 4, 1, 5] Output: 3 Explanation: One possible sequence:

• Remove [4] → array becomes [1, 3, 1, 5]
• Remove [1, 3, 1] → array becomes [5]
• Remove [5] → array is empty Total: 3 moves `

Example 3:

Input: arr = \[1, 2, 1\] Output: 1 Explanation: The entire array is a palindrome and can be removed in one move.