Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each column is judged independently: deleting another column cannot fix a decrease within this one. A column is sorted exactly when every character is at least the one immediately above it.

Approach

Scan each column from its second row downward. On the first adjacent decrease, count that column once and stop scanning it. Keep columns with no decrease. Equal characters are allowed, and a single-row grid needs no deletions. Return the total number of rejected columns.

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

        for c in range(cols):
            for r in range(1, rows):
                if strs[r][c] < strs[r - 1][c]:
                    res += 1
                    break

        return res

Complexity analysis

For R strings of length C, the nested scan takes O(RC) time and uses O(1) auxiliary space.