Code Implementation

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)
        m = len(strs[0])
        dp = [1] * m  # dp[j]: length of longest non-decreasing subsequence ending at column j

        for j in range(m):
            for i in range(j):
                if all(strs[row][i] <= strs[row][j] for row in range(n)):
                    dp[j] = max(dp[j], dp[i] + 1)
        return m - max(dp)
      

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size(), m = strs[0].size();
        vector<int> dp(m, 1);
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < j; ++i) {
                bool valid = true;
                for (int row = 0; row < n; ++row) {
                    if (strs[row][i] > strs[row][j]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        }
        return m - *max_element(dp.begin(), dp.end());
    }
};
      

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length, m = strs[0].length();
        int[] dp = new int[m];
        Arrays.fill(dp, 1);
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < j; ++i) {
                boolean valid = true;
                for (int row = 0; row < n; ++row) {
                    if (strs[row].charAt(i) > strs[row].charAt(j)) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }
        int max = 0;
        for (int x : dp) max = Math.max(max, x);
        return m - max;
    }
}
      

var minDeletionSize = function(strs) {
    const n = strs.length, m = strs[0].length;
    const dp = new Array(m).fill(1);
    for (let j = 0; j < m; ++j) {
        for (let i = 0; i < j; ++i) {
            let valid = true;
            for (let row = 0; row < n; ++row) {
                if (strs[row][i] > strs[row][j]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                dp[j] = Math.max(dp[j], dp[i] + 1);
            }
        }
    }
    return m - Math.max(...dp);
};
      

Problem Description

Given an array of equal-length strings strs, you are allowed to delete any subset of columns (i.e., the same index in every string). After deleting some columns, the remaining columns from left to right must keep the rows in lexicographical order (i.e., for every pair of rows, the sequence of their remaining characters must be non-decreasing from top to bottom).

Your task is to determine the minimum number of columns that must be deleted so that the rows of the resulting array are sorted lexicographically.

• You may delete any columns, but you must not rearrange them.
• There is one valid answer for each input.
• Each column can be deleted at most once.
• Do not reuse deleted columns.

Thought Process

At first glance, we might think to check each column and delete it if it causes any row to be out of order. However, because the problem allows us to delete any subset, and not just single columns, we need to consider how columns interact. For example, deleting one column can make another column "acceptable" to keep.

The brute-force approach would be to try all subsets of columns and check if the resulting matrix is sorted, but this is not efficient because there are 2^m subsets. We need to find a way to select the largest possible sequence of columns to keep, such that for every row, the sequence of kept columns is non-decreasing.

This is similar to finding the longest non-decreasing subsequence (LNDS) of columns, where the comparison is across all rows. The minimum columns to delete is then the total number of columns minus the length of this subsequence.

Solution Approach

Let's break down the solution step by step:

1. Observation: If we keep a set of columns in order, the rows must remain sorted. So, we want the largest ordered subset of columns where, for every row, the sequence of characters is non-decreasing.
2. Dynamic Programming: For each column j, we can check all previous columns i (where i < j) and see if, for every row, strs[row][i] <= strs[row][j]. If so, we can extend the subsequence ending at i to include j.
3. DP Array: We define dp[j] as the length of the longest non-decreasing subsequence ending at column j.
4. Transition: For each j, for each i < j, if all rows have strs[row][i] <= strs[row][j], update dp[j] = max(dp[j], dp[i] + 1).
5. Result: The answer is m - max(dp), where m is the total number of columns.

This approach efficiently finds the minimum columns to delete by maximizing the columns we can keep in order.

Example Walkthrough

Consider strs = ["ca","bb","ac"].

• Columns: 0 ('c','b','a'), 1 ('a','b','c')
• First, check if keeping both columns keeps the rows sorted:
  • Row 0: "ca"
  • Row 1: "bb"
  • Row 2: "ac"
  The order is: "ca", "bb", "ac" which is not sorted.
• Try deleting column 0:
  • Rows: "a", "b", "c" (sorted!)
• Try deleting column 1:
  • Rows: "c", "b", "a" (not sorted)
• So, the minimum is to delete column 0.
• Using the DP approach, dp[0]=1, dp[1]=1 (since 'c'<'a', not non-decreasing for all rows), so max(dp)=1, answer=2-1=1.

Time and Space Complexity

• Brute-force: O(2^m * n * m) - For each subset, check if the resulting rows are sorted.
• Optimized DP approach: O(m² * n) - For each pair of columns (i, j), check all rows.
• Space Complexity: O(m) for the DP array.

The DP approach is efficient for the problem's constraints.

Summary

The key insight is to maximize the number of columns we can keep in order, which is equivalent to finding the longest non-decreasing subsequence of columns where, for every row, the characters do not decrease. By using dynamic programming, we efficiently solve the problem in O(m²n) time, avoiding the combinatorial explosion of brute-force. This approach elegantly leverages subsequence logic across multiple strings, making it both efficient and conceptually satisfying.