Problem Statement in English

You’re given an array of n strings strs, all of the same length. We need to delete the minimum number of columns such that the remaining strings’ characters are lexicographically non-decreasing.

Return the minimum number of columns that need to be deleted.

Approach

This is one cool DP problem.

Couple things we need to keep in mind as we go into this:

  • If you think about it, we basically need an LIS (Longest Increasing Subsequence) on a per string basis (kind of)
  • It’s easier to come up with the number of columns to keep rather than the number of columns to delete

That’s it. Try it now.

For each column ($i^{th}$) we have to check all subsequent columns ($j^{th}$) on a per row basis to see if they can be kept.

If a pair of columns can be kept for every row in those columns, we can update our dp array.

Think about it - the dp update will be dp[i] = max(dp[i], 1 + dp[j]) where i is the current column and j is the subsequent column.

Finally, we return N - max(dp) where N is the total number of columns.

In my implementation the outer loop is reversed so that we can use previously computed dp values.

Solution in Python


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

        dp = [1] * N

        for i in reversed(range(N)):
            for j in range(i + 1, N):
                for row in strs:
                    if row[i] > row[j]:
                        break
                else:
                    dp[i] = max(dp[i], 1 + dp[j])

        return N - max(dp)

Complexity

  • Time: $O(N^2 \cdot M)$
    Since we have two nested loops iterating over the columns (N) and for each pair of columns, we are checking all rows (M) to see if the characters are in non-decreasing order.

  • Space: $O(N)$
    We are using a dp array of size N to store the length of the longest non-decreasing subsequence ending at each column.

Mistakes I Made

I had to look this one up :(

And we are done.