Code Implementation

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n, m = len(strs), len(strs[0])
        dp = [1] * m
        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 d : dp) max = Math.max(max, d);
        return m - max;
    }
}
      

var minDeletionSize = function(strs) {
    const n = strs.length, m = strs[0].length;
    const dp = 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

You are given an array strs where each element is a string of the same length. You can delete any number of columns from these strings (i.e., delete the same index from every string) so that the rows are lexicographically sorted. Your goal is to determine the minimum number of columns you must delete to achieve this.

• Each string in strs has the same length m.
• After deleting columns, the resulting array of strings (rows) must be sorted in lexicographical (dictionary) order.
• You may delete any subset of columns (possibly none or all), but the order of the remaining columns must be preserved.
• Return the minimum number of columns to delete so that the rows are sorted.

Thought Process

At first glance, the problem resembles sorting or checking order, but with the twist that you can delete columns. The naive approach would be to try every possible subset of columns and check if the resulting rows are sorted, but this is not feasible for large inputs since the number of subsets grows exponentially.

Instead, we can think of the problem as finding the largest set of columns (in order) that we can keep so that the rows are sorted, and then delete the rest. This is similar to the Longest Increasing Subsequence (LIS) problem, but in two dimensions: we want to find the longest sequence of columns such that, for every pair of columns in the sequence, the characters in all rows are non-decreasing.

By focusing on which columns to keep rather than which to delete, we turn the original problem into a maximization problem. The minimum number of deletions is then the total number of columns minus the size of the largest valid subsequence of columns.

Solution Approach

We solve the problem using dynamic programming, inspired by the Longest Increasing Subsequence (LIS) technique:

1. Define a DP array: Let dp[j] be the length of the longest valid sequence ending at column j.
2. Initialization: Start by setting all dp[j] to 1, since each column can be a sequence by itself.
3. Transition: For each column j, look at all previous columns i < j. If for every row r, strs[r][i] <= strs[r][j], then column j can follow column i in the sequence. In this case, update dp[j] as max(dp[j], dp[i] + 1).
4. Result: The answer is m - max(dp), where m is the total number of columns.

This approach ensures we only keep columns that maintain the required order in all rows, and we delete the minimal number of columns necessary.

Example Walkthrough

Let's consider strs = ["babca", "bbazb"].

• There are 2 rows and 5 columns (indices 0 to 4).
• We want to find the longest sequence of columns such that in every row, the sequence of characters is non-decreasing.
• Let's build dp step by step:
  • Column 0: "b", "b" — start, so dp[0] = 1.
  • Column 1: "a", "b" — compare to column 0:
    • Row 0: "b" (col 0) > "a" (col 1) — not non-decreasing, so can't extend.
    • So dp[1] = 1.
  • Column 2: "b", "a" — compare to previous columns:
    • With column 0: "b" <= "b" and "b" <= "a"? Row 1 fails, so can't extend.
    • With column 1: "a" <= "b" (row 0), "b" <= "a" (row 1) — row 1 fails, so can't extend.
    • So dp[2] = 1.
  • Column 3: "c", "z"
    • With column 0: "b" <= "c", "b" <= "z" — both pass, so dp[3] = dp[0] + 1 = 2.
    • With column 1: "a" <= "c", "b" <= "z" — both pass, so dp[3] = max(2, dp[1]+1)=2.
    • With column 2: "b" <= "c", "a" <= "z" — both pass, so dp[3] = max(2, dp[2]+1)=2.
  • Column 4: "a", "b"
    • With previous columns, check for non-decreasing in all rows.
    • Best is with column 1: "a" <= "a", "b" <= "b" — both pass, so dp[4] = dp[1] + 1 = 2.
• Final dp = [1, 1, 1, 2, 2], so the maximum is 2. We need to delete 5 - 2 = 3 columns.

Time and Space Complexity

• Brute-force approach: Try every subset of columns (2^m possibilities), and for each, check if the rows are sorted (O(nm) per check). This is exponential and infeasible for large m.
• Optimized DP approach:
  • For each column j, we compare to all previous columns i (O(m²)), and for each pair, we check all rows (O(n)).
  • Total time complexity: O(m²n)
  • Space complexity: O(m) for the DP array.

Summary

The problem is an application of the Longest Increasing Subsequence concept to columns of a string matrix, where the order must be maintained across all rows. By using dynamic programming, we efficiently find the largest set of columns to keep, ensuring the resulting rows are sorted, and thus minimize the number of columns to delete. This approach is both elegant and efficient, especially compared to the exponential brute-force solution.