leetcode

commit 708cfe4ba1c8aa16117ec272fb6b9f1d0eeab810
parent d728db446cb8f9a7f9bce4c3e580b9ded8210026
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 20 Dec 2025 19:51:59 -0700

955. delete columns to make sorted 2

Diffstat:
A
delete_columns_sorted2.c
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++
A
delete_columns_sorted2.py
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 91 insertions(+), 0 deletions(-)
diff --git a/delete_columns_sorted2.c b/delete_columns_sorted2.c
@@ -0,0 +1,46 @@
+// 955. Delete Columns to Make Sorted II
+#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. for example, if we have 'strs = [abcdef, uvwxyz]' and
+ * deletion indices '1, 2, 3', then the final array after deletions is '[bef,
+ * vyz]'. suppose we chose a set of deletion indices 'answer' such that after
+ * deletions, the final array has its elements in lexographic order. return the
+ * minimum possible value of 'ans.len'.
+ */
+
+int minDeletionSize(char **strs, int strsSize) {
+  int n = strsSize, m = strlen(strs[0]);
+  int unresolved = n - 1, ans = 0;
+  bool *resolved = (bool *)calloc(n - 1, sizeof(int));
+  for (int i = 0; i < m && unresolved > 0; i++) {
+    bool need = false;
+    for (int j = 0; j < n - 1; j++)
+      if (!resolved[j] && strs[j][i] > strs[j + 1][i]) {
+        need = true;
+        break;
+      }
+    if (need) {
+      ans++;
+      continue;
+    }
+    for (int j = 0; j < n - 1; j++)
+      if (!resolved[j] && strs[j][i] < strs[j + 1][i]) {
+        resolved[j] = true;
+        unresolved--;
+      }
+  }
+  free(resolved);
+  return ans;
+}
+
+int main() {
+  char *s1[] = {"ca", "bb", "ac"};
+  char *s2[] = {"xc", "yb", "za"};
+  char *s3[] = {"zyx", "wvu", "tsr"};
+  printf("%d\n", minDeletionSize(s1, ARRAY_SIZE(s1))); // expect: 1
+  printf("%d\n", minDeletionSize(s2, ARRAY_SIZE(s2))); // expect: 0
+  printf("%d\n", minDeletionSize(s3, ARRAY_SIZE(s3))); // expect: 3
+}
diff --git a/delete_columns_sorted2.py b/delete_columns_sorted2.py
@@ -0,0 +1,45 @@
+# 955. Delete Columns to Make Sorted II
+
+"""
+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. for example, if we have 'strs = [abcdef, uvwxyz]' and
+deletion indices '1, 2, 3', then the final array after deletions is '[bef,
+vyz]'. suppose we chose a set of deletion indices 'answer' such that after
+deletions, the final array has its elements in lexographic order. return the
+minimum possible value of 'ans.len'.
+"""
+
+
+class Solution(object):
+    def minDeletionSize(self, strs):
+        """
+        :type strs: List[str]
+        :rtype: int
+        """
+        n, m = len(strs), len(strs[0])
+        unresolved, ans = n - 1, 0
+        resolved = [False] * (n - 1)
+        for i in range(m):
+            if unresolved == 0:
+                break
+            need = False
+            for j in range(n - 1):
+                if not resolved[j] and strs[j][i] > strs[j + 1][i]:
+                    need = True
+                    break
+            if need:
+                ans += 1
+                continue
+            for j in range(n - 1):
+                if not resolved[j] and strs[j][i] < strs[j + 1][i]:
+                    resolved[j] = True
+                    unresolved -= 1
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minDeletionSize(strs=["ca", "bb", "ac"]))
+    print(obj.minDeletionSize(strs=["xc", "yb", "za"]))
+    print(obj.minDeletionSize(strs=["zyx", "wvu", "tsr"]))