Watch 10 video solutions for Delete Columns to Make Sorted III, a hard level problem involving Array, String, Dynamic Programming. This walkthrough by codestorywithMIK has 6,070 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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, 3}, then the final array after deletions is ["bef", "vyz"].
Suppose we chose a set of deletion indices answer such that after deletions, the final array has every string (row) in lexicographic order. (i.e., (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]), and (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]), and so on). Return the minimum possible value of answer.length.
Example 1:
Input: strs = ["babca","bbazb"] Output: 3 Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"]. Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]). Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.
Example 2:
Input: strs = ["edcba"] Output: 4 Explanation: If we delete less than 4 columns, the only row will not be lexicographically sorted.
Example 3:
Input: strs = ["ghi","def","abc"] Output: 0 Explanation: All rows are already lexicographically sorted.
Constraints:
n == strs.length1 <= n <= 1001 <= strs[i].length <= 100strs[i] consists of lowercase English letters.Problem Overview: You are given an array of equal-length strings. Each column represents characters from all rows at the same index. The goal is to delete the minimum number of columns so that every row becomes lexicographically non‑decreasing from left to right.
The key observation: after deletions, the remaining columns must form a sequence where every row stays sorted. Instead of directly deciding which columns to remove, treat it as finding the longest valid sequence of columns that keeps all rows sorted. The answer is total columns minus that sequence length.
Approach 1: Dynamic Programming (Column LIS) (Time: O(m² * n), Space: O(m))
This is the standard optimal approach. Treat each column like an element in a Longest Increasing Subsequence problem. Let dp[j] represent the maximum number of valid columns ending at column j. For every pair of columns i < j, check whether column i can appear before column j. This requires verifying that for every row r, strs[r][i] <= strs[r][j]. If the condition holds for all rows, update dp[j] = max(dp[j], dp[i] + 1). The longest valid subsequence across columns gives the maximum columns we can keep. The minimum deletions become m - max(dp). This method leverages Dynamic Programming and works well because column count is usually small enough for the quadratic comparison.
Approach 2: Greedy with Column Comparison (Time: O(m² * n), Space: O(1))
This strategy incrementally builds a set of kept columns. For each new column, compare it with previously kept columns to verify whether adding it preserves lexicographic order across every row. The algorithm iterates through rows and checks character ordering for each candidate pair of columns. If any row violates the order, that column must be skipped (effectively deleted). While conceptually simple, repeated column comparisons can still lead to quadratic checks over columns. It relies heavily on character comparisons within the String structure and column traversal through the Array of strings.
Recommended for interviews: The dynamic programming formulation is what most interviewers expect. Recognizing that the problem reduces to a longest increasing subsequence across columns demonstrates strong problem decomposition. The greedy comparison approach helps build intuition but doesn’t clearly express the optimal subsequence structure. Showing both ideas — brute reasoning followed by the DP optimization — signals solid algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Column LIS) | O(m² * n) | O(m) | General case and interview settings where optimal subsequence detection is required |
| Greedy Column Comparison | O(m² * n) | O(1) | Conceptual approach for understanding column ordering without maintaining DP state |