Delete Columns to Make Sorted III — Hard Problem & Solution

Problem statement

You are given n strings strs of equal length. You may choose a set of column indices and delete those characters from every string.

After the deletion, each string on its own must be sorted: its letters appear in non-decreasing alphabetical order from left to right. (The strings do not need to be in any order relative to each other.)

Return the minimum number of columns to delete.

Example 1

Input: strs = ["kairo","codes"]
Output: 3
Explanation: Keeping columns 2 and 3 leaves `"ir"` and `"de"`, both sorted; no three columns work for both rows.

Example 2

Input: strs = ["dcba"]
Output: 3

Example 3

Input: strs = ["abc","bcd","xyz"]
Output: 0

Constraints

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters

How to solve Delete Columns to Make Sorted III

Treat each column as an element and call i < j compatible when all rows are non-decreasing from column i to column j. We need the longest chain of pairwise-consecutive compatible columns — an LIS-style DP.

Approach

1. Let m be the string length and dp[j] = 1 for all j.
2. For each j and each i < j: if strs[r][i] <= strs[r][j] for every row r, set dp[j] = max(dp[j], dp[i] + 1).
3. Return m - max(dp).

Why it works

A set of kept columns leaves every row sorted exactly when each consecutive pair of kept columns is compatible (sortedness is checked between neighbours). So the kept set is a chain in the compatibility relation, and dp[j] is the longest such chain ending at j, built from the best chain ending at some compatible earlier column.

Complexity

• Time — O(n · m^2)
• Space — O(m)

Pitfalls

• Compatibility must hold in every row at once, not just in one.
• Only consecutive kept columns need to be compared — no need to check all pairs within the chain.
• Equal letters are allowed (non-decreasing), so use <=.

Reference solution

Python

from typing import List

def minDeletionSize(strs: List[str]) -> int:
    m = len(strs[0])
    dp = [1] * m
    for j in range(m):
        for i in range(j):
            if all(s[i] <= s[j] for s in strs):
                dp[j] = max(dp[j], dp[i] + 1)
    return m - max(dp)

JavaScript

var minDeletionSize = function(strs) {
    var n = strs.length, m = strs[0].length;
    var dp = new Array(m).fill(1);
    var best = 0;
    for (var j = 0; j < m; j++) {
        for (var i = 0; i < j; i++) {
            var ok = true;
            for (var r = 0; r < n; r++) if (strs[r][i] > strs[r][j]) { ok = false; break; }
            if (ok && dp[i] + 1 > dp[j]) dp[j] = dp[i] + 1;
        }
        if (dp[j] > best) best = dp[j];
    }
    return m - best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Remove Boxes Hard
• Number of Squareful Arrays Hard
• Closest Subsequence Sum Hard
• Maximum Number of Achievable Transfer Requests Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard