Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Here each row must be nondecreasing after the same columns are deleted. Equivalently, keep the longest subsequence of columns whose values never decrease in any row. Two retained columns are compatible only when every row agrees on their order.

Approach

Initialize every column's best length to one. For an earlier column a and a later column b, require strs[r][a] <= strs[r][b] in every row. Python scans right to left and stores the best subsequence starting at each column, updating dp[a] with 1 + dp[b]. JavaScript scans left to right and stores the best subsequence ending at each column, updating dp[b] with 1 + dp[a]. In either case, retain the larger length. Compatibility is transitive, so checking consecutive retained columns suffices. Return the total column count minus the largest DP value.

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        cols = len(strs[0])
        rows = len(strs)
        dp = [1] * cols

        for c1 in range(cols - 2, -1, -1):
            for c2 in range(c1 + 1, cols):
                valid = True
                for r in range(rows):
                    if strs[r][c1] > strs[r][c2]:
                        valid = False
                        break
                if valid:
                    dp[c1] = max(dp[c1], 1 + dp[c2])

        return cols - max(dp)

Complexity analysis

For R strings and C columns, the DP tests O(C²) column pairs and scans all R rows for each pair. Time is O(RC²) and auxiliary space is O(C).