Delete Columns to Make Sorted III

Hard
1462.

Delete Columns to Make Sorted III

Delete Columns to Make Sorted III is a hard coding problem on arrays, strings and dynamic programming, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} strs
 * @return {number}
 */
var minDeletionSize = function(strs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete Columns to Make Sorted III — Problem & Solution

Delete Columns to Make Sorted III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Delete Columns to Make Sorted III is a hard coding problem on arrays, strings and dynamic programming, asked in Amazon and Google interviews.

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

Hints for Delete Columns to Make Sorted III

  1. Hint 1

    Minimising deletions is the same as maximising the number of kept columns.

  2. Hint 2

    Kept columns i < j are compatible when every row has strs[r][i] <= strs[r][j]. This is a longest-increasing-subsequence problem over columns.

  3. Hint 3

    dp[j] = most columns you can keep ending with column j = 1 + max(dp[i]) over compatible i < j. Answer: length - max(dp).

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)

Java

public static int minDeletionSize(String[] strs) {
    int n = strs.length, m = strs[0].length();
    int[] dp = new int[m];
    int best = 0;
    for (int j = 0; j < m; j++) {
        dp[j] = 1;
        for (int i = 0; i < j; i++) {
            boolean ok = true;
            for (int r = 0; r < n; r++) if (strs[r].charAt(i) > strs[r].charAt(j)) { ok = false; break; }
            if (ok) dp[j] = Math.max(dp[j], dp[i] + 1);
        }
        best = Math.max(best, dp[j]);
    }
    return m - best;
}

C++

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

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings