Delete Columns to Make Sorted III LeetCode solution in Python

1
class Solution:
2
    def minDeletionSize(self, strs: List[str]) -> int:
3
        n = len(strs[0])
4
        dp = [1] * n
5
        for i in range(1, n):
6
            for j in range(i):
7
                valid = True
8
                for a in strs:
9
                    if a[j] > a[i]:
10
                        valid = False
11
                        break
12
                if valid:
13
                    dp[i] = max(dp[i], dp[j] + 1)
14
        return n - max(dp)