Given an array arr[] consisting of N elements, the task is to find the minimum palindromic subarray removals required to remove all elements from the array.
Examples:
Input: arr[] = {1, 3, 4, 1, 5}, N = 5
Output: 3
Explanation:
Removal of 4 from the array leaves {1, 3, 1, 5}.
Removal of {1, 3, 1} leaves {5}.
Removal of 5 makes the array empty.
Input: arr[] = {1, 2, 3, 5, 3, 1}, N = 5
Output: 2
Explanation:
Removal of {3, 5, 3} leaves {1, 2, 1}.
Removal of {1, 2, 1} makes the array empty.
Approach:
We can use Interval Dynamic Programming to solve this problem. Follow the steps below to solve the problem:
- Initialize dp[][] such that every dp[i][j] represents the minimum number of removals required from the ith position to the jth position.
- For the interval from i to j, the answer may be the sum of the two intervals from i to k and k + 1 to j, that is:
dp [i][j]= minimum (dp [i][j], dp [i][k] + dp [k + 1][j]) where i ? k <j
- In addition to this possibility, we need to check if arr[i] = arr[j], then dp[i][j] = dp[i + 1][j – 1].
Below is the implementation of the above approach:
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; int dp[550][550]; int minSubarrayRemoval(vector< int >& arr) { int i, j, k, l; int n = arr.size(); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { dp[i][j] = n; } } for (i = 0; i < n; i++) { dp[i][i] = 1; } for (i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { dp[i][i + 1] = 1; } else { dp[i][i + 1] = 2; } } for (l = 2; l < n; l++) { for (i = 0; i + l < n; i++) { j = i + l; if (arr[i] == arr[j]) { dp[i][j] = dp[i + 1][j - 1]; } for (k = i; k < j; k++) { dp[i][j] = min( dp[i][j], dp[i][k] + dp[k + 1][j]); } } } return dp[0][n - 1]; } // Driver Program int main() { vector< int > arr = { 2, 3, 1, 2, 2, 1, 2 }; int ans = minSubarrayRemoval(arr); cout << ans << endl; } |
Java
// Java program for the above approach class GFG{ static int dp[][] = new int [ 550 ][ 550 ]; static int minSubarrayRemoval( int arr[]) { int i, j, k, l; int n = arr.length; for (i = 0 ; i < n; i++) { for (j = 0 ; j < n; j++) { dp[i][j] = n; } } for (i = 0 ; i < n; i++) { dp[i][i] = 1 ; } for (i = 0 ; i < n - 1 ; i++) { if (arr[i] == arr[i + 1 ]) { dp[i][i + 1 ] = 1 ; } else { dp[i][i + 1 ] = 2 ; } } for (l = 2 ; l < n; l++) { for (i = 0 ; i + l < n; i++) { j = i + l; if (arr[i] == arr[j]) { dp[i][j] = dp[i + 1 ][j - 1 ]; } for (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 ]; } // Driver code public static void main (String[] args) { int arr [] = new int []{ 2 , 3 , 1 , 2 , 2 , 1 , 2 }; int ans = minSubarrayRemoval(arr); System.out.println(ans); } } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approach def minSubarrayRemoval(arr): n = len (arr) dp = [] for i in range (n): l = [ 0 ] * n for j in range (n): l[j] = n dp.append(l) for i in range (n): dp[i][i] = 1 for i in range (n - 1 ): if (arr[i] = = arr[i + 1 ]): dp[i][i + 1 ] = 1 else : dp[i][i + 1 ] = 2 for l in range ( 2 , n): for i in range (n - l): j = i + l if (arr[i] = = arr[j]): dp[i][j] = dp[i + 1 ][j - 1 ] for k in range (i, j): dp[i][j] = min (dp[i][j], dp[i][k] + dp[k + 1 ][j]) return dp[ 0 ][n - 1 ] # Driver code arr = [ 2 , 3 , 1 , 2 , 2 , 1 , 2 ] ans = minSubarrayRemoval(arr) print (ans) # This code is contributed by shubhamsingh10 |
C#
// C# program for the above approach using System; class GFG{ static int [,]dp = new int [550, 550]; static int minSubarrayRemoval( int []arr) { int i, j, k, l; int n = arr.Length; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { dp[i, j] = n; } } for (i = 0; i < n; i++) { dp[i, i] = 1; } for (i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { dp[i, i + 1] = 1; } else { dp[i, i + 1] = 2; } } for (l = 2; l < n; l++) { for (i = 0; i + l < n; i++) { j = i + l; if (arr[i] == arr[j]) { dp[i, j] = dp[i + 1, j - 1]; } for (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]; } // Driver code public static void Main() { int []arr = new int []{ 2, 3, 1, 2, 2, 1, 2 }; int ans = minSubarrayRemoval(arr); Console.Write(ans); } } // This code is contributed by Code_Mech |
Javascript
<script> // JavaScript program for the above approach let dp = new Array(550); // Loop to create 2D array using 1D array for ( var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } function minSubarrayRemoval(arr) { let i, j, k, l; let n = arr.length; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { dp[i][j] = n; } } for (i = 0; i < n; i++) { dp[i][i] = 1; } for (i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { dp[i][i + 1] = 1; } else { dp[i][i + 1] = 2; } } for (l = 2; l < n; l++) { for (i = 0; i + l < n; i++) { j = i + l; if (arr[i] == arr[j]) { dp[i][j] = dp[i + 1][j - 1]; } for (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]; } // Driver Code let arr = [ 2, 3, 1, 2, 2, 1, 2 ]; let ans = minSubarrayRemoval(arr); document.write(ans); </script> |
2
Time Complexity: O(n3), where n is the length of the array.
Auxiliary Space: O(n2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!