Delete Columns to Make Sorted II

lcpy gen -n 955   # by problem number
lcpy gen -s delete_columns_to_make_sorted_ii   # by problem name

Input: strs = ["ca","bb","ac"]
Output: 1
Explanation: After deleting the first column, strs = ["a", "b", "c"]. Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]). We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.

Input: strs = ["xc","yb","za"]
Output: 0
Explanation: strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= ...)

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: We have to delete every column.

class Solution:
    # Time: O(n * w^2)
    # Space: O(n * w)
    def min_deletion_size(self, strs: list[str]) -> int:
        keep = [""] * len(strs)
        deleted = 0
        for j in range(len(strs[0])):
            candidate = [row + s[j] for row, s in zip(keep, strs, strict=True)]
            if all(candidate[i] <= candidate[i + 1] for i in range(len(candidate) - 1)):
                keep = candidate
            else:
                deleted += 1
        return deleted