Palindrome Removal
MicrosoftThe 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.
Input: arr = [1,3,4,1,5] Output: 3 Explanation: Remove [4] then remove [1,3,1] then remove [5].
Input: arr = [1,2] Output: 2
Input: arr = [1,2,3,2,1]
- 1 <= arr.length <= 100
- 1 <= arr[i] <= 20
cpp
class Solution {
public:
int minimumMoves(vector<int>& arr) {
// User code goes here
}
};java
class Solution {
public int minimumMoves(int[] arr) {
// Implement the logic here
return 0;
}
}python
class Solution:
def minimumMoves(self, arr):
#User code goes herejavascript
class Solution {
minimumMoves(arr) {
// User code goes here
}
}csharp
public class Solution
{
public int MinimumMoves(int[] arr)
{
int n = arr.Length;
int[,] dp = new 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 <= n - len; i++)
{
int j = i + len - 1;
dp[i, j] = len;
if (arr[i] == arr[j])
{
dp[i, j] = (i + 1 <= j - 1) ? dp[i + 1, j - 1] : 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];
}
}go
func minimumMoves(arr []int) int {
//your code goes here
}Stuck? Show a way to structure it+
- 01Define a minimum-moves interval state.
- 02Use an empty-range base case.
- 03Remove the first value alone initially.
- 04Merge equal endpoints through cleared middles.
- 05Take the minimum transition.
Reference answer
Then expect these follow-ups
How would you reconstruct removals?
Tests: choices
What is the palindrome special case?
Tests: simplification
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question