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;
    const m = strs[0].length;

    // sorted[i] = true means strs[i] < strs[i+1] is already determined
    const sorted = Array(n - 1).fill(false);

    let deletions = 0;

    // Scan columns left to right
    for (let col = 0; col < m; col++) {

        // Check if keeping this column would break lexicographic order
        let mustDelete = false;

        for (let i = 0; i < n - 1; i++) {
            // Only check pairs that are still tied
            if (!sorted[i]) {
                const a = strs[i][col];
                const b = strs[i + 1][col];

                // If this column breaks order, we must delete it
                if (a > b) {
                    mustDelete = true;
                    break;
                }
            }
        }

        // If column must be deleted, skip updating sorted[]
        if (mustDelete) {
            deletions++;
            continue;
        }

        // Otherwise, update sorted[]:
        // Any pair where a < b becomes permanently sorted
        for (let i = 0; i < n - 1; i++) {
            if (!sorted[i]) {
                const a = strs[i][col];
                const b = strs[i + 1][col];

                if (a < b) {
                    sorted[i] = true;
                }
            }
        }
    }

    return deletions;
};