You are given an array of n strings strs, all of the same length. We may choose any deletion indices, and we delete all the characters in those indices for each string. For example, if we have strs = ["abcdef","uvwxyz"] and deletion indices {0, 2,

minDeletionSize.js

/**
 * @param {string[]} strs
 * @return {number}
 */
var minDeletionSize = function(strs) {
    const n = strs.length;        // number of rows
    const m = strs[0].length;     // number of columns (all strings same length)

    // dp[i] = length of the longest valid chain ending at column i
    const dp = Array(m).fill(1);

    // Helper: check if column j can come before column i
    // This requires strs[row][j] <= strs[row][i] for EVERY row
    function isValid(j, i) {
        for (let row = 0; row < n; row++) {
            if (strs[row][j] > strs[row][i]) {
                return false; // violates non-decreasing order for this row
            }
        }
        return true;
    }

    // Build the DP table (LIS-like logic)
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < i; j++) {
            // If column j can precede column i, update dp[i]
            if (isValid(j, i)) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    // Longest chain of columns we can keep
    const longest = Math.max(...dp);

    // Minimum deletions = total columns - longest valid chain
    return m - longest;
};