Delete Columns to Make Sorted III

hard dynamic programming LIS string

Problem

You are given an array of n strings strs, all of the same length. You may delete any set of columns (a column is the set of characters at one index across every string). After deleting, every remaining row strs[i] must be in non-decreasing alphabetical order. Return the minimum number of columns you must delete.

Inputstrs = ["babca", "bbazb"]

Output3

Keep columns 0 and 4 ("ba" and "bb" — both rows sorted). 5 columns − 2 kept = 3 deleted.

strs (comma-separated, equal length)

def min_deletion_size(strs):
    w = len(strs[0])
    dp = [1] * w
    for j in range(w):
        for i in range(j):
            if all(s[i] <= s[j] for s in strs):
                dp[j] = max(dp[j], dp[i] + 1)
    return w - max(dp)

function minDeletionSize(strs) {
  const w = strs[0].length;
  const dp = new Array(w).fill(1);
  for (let j = 0; j < w; j++) {
    for (let i = 0; i < j; i++) {
      if (strs.every(s => s[i] <= s[j])) {
        dp[j] = Math.max(dp[j], dp[i] + 1);
      }
    }
  }
  return w - Math.max(...dp);
}

class Solution {
    public int minDeletionSize(String[] strs) {
        int w = strs[0].length();
        int[] dp = new int[w];
        java.util.Arrays.fill(dp, 1);
        int best = 1;
        for (int j = 0; j < w; j++) {
            for (int i = 0; i < j; i++) {
                boolean ok = true;
                for (String s : strs)
                    if (s.charAt(i) > s.charAt(j)) { ok = false; break; }
                if (ok) dp[j] = Math.max(dp[j], dp[i] + 1);
            }
            best = Math.max(best, dp[j]);
        }
        return w - best;
    }
}

int minDeletionSize(vector<string>& strs) {
    int w = strs[0].size();
    vector<int> dp(w, 1);
    int best = 1;
    for (int j = 0; j < w; j++) {
        for (int i = 0; i < j; i++) {
            bool ok = true;
            for (auto& s : strs)
                if (s[i] > s[j]) { ok = false; break; }
            if (ok) dp[j] = max(dp[j], dp[i] + 1);
        }
        best = max(best, dp[j]);
    }
    return w - best;
}

Explanation

Instead of thinking about which columns to delete, flip it around: which columns can we keep? We want the largest set of columns that, when read left to right, leaves every row sorted. Then the answer is total columns minus that largest keepable set.

This is a longest increasing subsequence over columns. We define dp[j] as the longest run of kept columns ending at column j, where for any earlier kept column i the characters at i are <= the characters at j in every row.

For each j we look back at every i < j; if column i can legally precede j (all rows have s[i] <= s[j]), we can extend that run, so dp[j] = max(dp[j], dp[i] + 1). Every dp[j] starts at 1 since a single column is always keepable.

Example: strs = ["babca", "bbazb"]. Columns 0 and 4 read "ba"/"bb" — both rows non-decreasing — so the longest keepable run is 2. With 5 columns total, we delete 5 - 2 = 3.

The compatibility check scans all n rows, and we compare every pair of columns, so the cost is about n · w².

Time: O(n · w²) Space: O(w)