Palindrome Removal in C++

Suppose we have an integer array called arr, now in one move we can select a palindromic subarray from index i to j where i <= j, and remove that subarray from the given array. We have to keep in mind 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. We have to find the minimum number of moves needed to remove all numbers from the array.

So, if the input is like arr = [1,3,4,1,5], then the output will be 3, as we can remove in this sequence, remove [4] then remove [1,3,1] then remove [5].

To solve this, we will follow these steps −

• n := size of arr

• Define one 2D array dp of size (n + 1) x (n + 1)

• for initialize l := 1, when l <= n, update (increase l by 1), do −

  • for initialize i := 0, j := l - 1, when j < n, update (increase i by 1), (increase j by 1), do −

    • if l is same as 1, then −

      • dp[i, j] := 1

    • Otherwise

      • dp[i, j] := 1 + dp[i + 1, j]

      • if i + 1 < n and arr[i] is same as arr[i + 1], then −

        • dp[i, j] := minimum of dp[i, j] and 1 + dp[i + 2, j]

      • for initialize k := i + 2, when k <= j, update (increase k by 1), do −

        • if arr[i] is same as arr[k], then −

          • dp[i, j] := minimum of dp[i, j] and dp[i + 1, k - 1] + dp[k + 1, j]

• return dp[0, n - 1]

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minimumMoves(vector<int>& arr) {
      int n = arr.size();
      vector<vector<int> > dp(n + 1, vector<int>(n + 1));
      for (int l = 1; l <= n; l++) {
         for (int i = 0, j = l - 1; j < n; i++, j++) {
            if (l == 1) {
               dp[i][j] = 1;
            } else {
               dp[i][j] = 1 + dp[i + 1][j];
               if (i + 1 < n && arr[i] == arr[i + 1])
               dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]);
               for (int k = i + 2; k <= j; k++) {
                  if (arr[i] == arr[k]) {
                     dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);
                  }
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2};
   cout << (ob.minimumMoves(v));
}

Input

[1,2]

Output

2