leetcode

commit d7a284890aaa5bb228ad65f09ad9d10181550485
parent 708cfe4ba1c8aa16117ec272fb6b9f1d0eeab810
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun, 21 Dec 2025 20:09:52 -0700

960. delete columns to make sorted 3

Diffstat:
A
delete_columns_sorted3.c
 | 
42
++++++++++++++++++++++++++++++++++++++++++
A
delete_columns_sorted3.py
 | 
31
+++++++++++++++++++++++++++++++

2 files changed, 73 insertions(+), 0 deletions(-)
diff --git a/delete_columns_sorted3.c b/delete_columns_sorted3.c
@@ -0,0 +1,42 @@
+// 960. Delete Columns to Make Sorted III
+#include "leetcode.h"
+
+/*
+ * you are given an array of 'n' strings 'strs', all of the same length. we may
+ * choose any deletion indices and we delete all the characters in those indices
+ * for each string. suppose we chose a set of deletion indices 'answer' such
+ * that after deletions, the final array has every string (row) in lexicographic
+ * order. return the minimum possible value of 'ans.length'.
+ */
+
+int minDeletionSize(char **strs, int strsSize) {
+  int n = strlen(strs[0]), *dp = (int *)malloc(n * sizeof(int));
+  for (int i = 0; i < n; i++)
+    dp[i] = 1;
+  for (int i = 1; i < n; i++) {
+    for (int j = 0; j < i; j++) {
+      bool valid = true;
+      for (int k = 0; k < strsSize; k++)
+        if (strs[k][j] > strs[k][i]) {
+          valid = false;
+          break;
+        }
+      if (valid && dp[i] < dp[j] + 1)
+        dp[i] = dp[j] + 1;
+    }
+  }
+  int max = 0;
+  for (int i = 0; i < n; i++)
+    max = fmax(max, dp[i]);
+  free(dp);
+  return n - max;
+}
+
+int main() {
+  char *s1[] = {"babca", "bbazb"};
+  char *s2[] = {"edcba"};
+  char *s3[] = {"ghi", "def", "abc"};
+  printf("%d\n", minDeletionSize(s1, ARRAY_SIZE(s1))); // expect: 3
+  printf("%d\n", minDeletionSize(s2, ARRAY_SIZE(s2))); // expect: 4
+  printf("%d\n", minDeletionSize(s3, ARRAY_SIZE(s3))); // expect: 0
+}
diff --git a/delete_columns_sorted3.py b/delete_columns_sorted3.py
@@ -0,0 +1,31 @@
+# 960. Delete Columns to Make Sorted III
+
+"""
+you are given an array of 'n' strings 'strs', all of the same length. we may
+choose any deletion indices and we delete all the characters in those indices
+for each string. suppose we chose a set of deletion indices 'answer' such
+that after deletions, the final array has every string (row) in lexicographic
+order. return the minimum possible value of 'ans.length'.
+"""
+
+
+class Solution(object):
+    def minDeletionSize(self, strs):
+        """
+        :type strs: List[str]
+        :rtype: int
+        """
+        n = len(strs[0])
+        dp = [1] * n
+        for j in range(1, n):
+            for i in range(j):
+                if all(s[i] <= s[j] for s in strs):
+                    dp[j] = max(dp[j], dp[i] + 1)
+        return n - max(dp)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minDeletionSize(strs=["babca", "bbazb"]))
+    print(obj.minDeletionSize(strs=["edcba"]))
+    print(obj.minDeletionSize(strs=["ghi", "def", "abc"]))