Problem Statement in English

You are given an array of n strings strs, all of the same length.

You need to delete the minimum number of columns such that each row is in non-decreasing sorted order from top to bottom.

Return the number of columns that you will delete.

Approach

For each column, we will check if the characters in that column are sorted in non-decreasing order. If we find any character that is smaller than the character in the previous row for that column, we will increment our deletion count, and move to the next column.

If the column is sorted, we will simply move to the next column without incrementing the deletion count.

Solution in Python


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

        while col < l:
            for i in range(1, len(strs)):
                prev = strs[i - 1][col]
                this = strs[i][col]

                if prev > this:
                    res += 1
                    break
            col += 1

        return res

Complexity

  • Time: $O(n \times m)$
    Where n is the number of strings and m is the length of each string.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space.

And we are done.