Add solution #1246

JoshCrozier · JoshCrozier · commit 116ad1a7404c · 2025-06-29T23:17:40.000-05:00
diff --git a/README.md b/README.md
@@ -1156,6 +1156,7 @@
 1243|[Array Transformation](./solutions/1243-array-transformation.js)|Easy|
 1244|[Design A Leaderboard](./solutions/1244-design-a-leaderboard.js)|Medium|
 1245|[Tree Diameter](./solutions/1245-tree-diameter.js)|Medium|
+1246|[Palindrome Removal](./solutions/1246-palindrome-removal.js)|Hard|
 1247|[Minimum Swaps to Make Strings Equal](./solutions/1247-minimum-swaps-to-make-strings-equal.js)|Medium|
 1248|[Count Number of Nice Subarrays](./solutions/1248-count-number-of-nice-subarrays.js)|Medium|
 1249|[Minimum Remove to Make Valid Parentheses](./solutions/1249-minimum-remove-to-make-valid-parentheses.js)|Medium|
diff --git a/solutions/1246-palindrome-removal.js b/solutions/1246-palindrome-removal.js
@@ -0,0 +1,47 @@
+/**
+ * 1246. Palindrome Removal
+ * https://leetcode.com/problems/palindrome-removal/
+ * Difficulty: Hard
+ *
+ * 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.
+ */
+
+/**
+ * @param {number[]} arr
+ * @return {number}
+ */
+var minimumMoves = function(arr) {
+  const n = arr.length;
+  const dp = new Array(n).fill().map(() => new Array(n).fill(Infinity));
+
+  for (let i = 0; i < n; i++) {
+    dp[i][i] = 1;
+  }
+
+  for (let length = 2; length <= n; length++) {
+    for (let i = 0; i <= n - length; i++) {
+      const j = i + length - 1;
+
+      if (arr[i] === arr[j]) {
+        if (length === 2) {
+          dp[i][j] = 1;
+        } else {
+          dp[i][j] = dp[i + 1][j - 1];
+        }
+      }
+
+      for (let 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];
+};
