Delete Columns to Make Sorted III

lcpy gen -n 960   # by problem number
lcpy gen -s delete_columns_to_make_sorted_iii   # by problem name

Input: strs = ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).
Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.

Input: strs = ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row will not be lexicographically sorted.

Input: strs = ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.

class Solution:
    # Time: O(m^2 * n) where m is column count and n is row count
    # Space: O(m)
    def min_deletion_size(self, strs: list[str]) -> int:
        rows = len(strs)
        cols = len(strs[0])
        # best[j] = max number of columns we can keep ending with column j
        best = [1] * cols
        for j in range(cols):
            for i in range(j):
                if all(strs[r][i] <= strs[r][j] for r in range(rows)):
                    best[j] = max(best[j], best[i] + 1)
        return cols - max(best)