Leetcode 0960. Delete Columns to Make Sorted III

Problem statement

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/

Solution

This is in fact LIS problem but for strings.

Complexity

Time complexity is O(m^2 * n), space is O(m).

Code

class Solution:
    def minDeletionSize(self, A):
        n, m = len(A), len(A[0])
        
        dp = [1] * m
        for i in range(1, m):
            for j in range(i):
                if all(A[k][j] <= A[k][i] for k in range(n)):
                    dp[i] = max(dp[i], dp[j] + 1)
                    
        return m - max(dp)