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.
This approach utilizes dynamic programming to identify the minimum columns to delete to make each row lexicographically sorted. The key idea is to use a dp array where dp[j] represents the length of the longest increasing subsequence of columns ending at index j.
We'll iterate over each column and compare with the previous columns to update the dp array by checking each row for their lexicographic order. We finally return the total number of columns minus the maximum value in the dp array, which gives the least number of deletions needed.
The C code implements a dynamic programming solution. It initializes a dp array to track the longest increasing subsequence of column indices which maintain the row order. For each pair of columns, it checks if swapping the columns maintains the lexicographic order in each row. The solution updates the dp array accordingly and returns the total columns minus the maximum value in this array.
Time Complexity: O(n^2 * m), where n is the length of each string and m is the number of strings.
Space Complexity: O(n) for the dp array.
This approach involves a greedy strategy where we incrementally build the sorted subset of columns. By comparing columns, we find those that necessarily break the order when removed and only retain these to maintain row order.
At each step, the algorithm compares characters in successive columns, choosing deletions based on maintaining an overall least sequence of lexicographically ordered characters per row.
In this greedy C solution, we traverse each column, comparing successive characters for lexicographic order. If for any column, the order breaks, the column is marked for deletion, thereby incrementing the answer tally, which is returned as the result.
Time Complexity: O(m * n), where m is the number of strings and n is the length of each string.
Space Complexity: O(1), as only constant space is used.
We define f[i] as the length of the longest non-decreasing subsequence ending at column i. Initially, f[i] = 1, and the final answer is n - max(f).
To compute f[i], we iterate over all j < i. If for all strings s, we have s[j] leq s[i], then we update f[i] as follows:
$ f[i] = max(f[i], f[j] + 1)
Finally, we return n - max(f).
The time complexity is O(n^2 times m), and the space complexity is O(n), where n is the length of each string in the array strs, and m$ is the number of strings in the array.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2 * m), where n is the length of each string and m is the number of strings. |
| Greedy Approach with Column Comparison | Time Complexity: O(m * n), where m is the number of strings and n is the length of each string. |
| Dynamic Programming | — |
| 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 |
Delete Columns to Make Sorted III | Hard Made Easy | Dry Run | Leetcode 960 | codestorywithMIK • codestorywithMIK • 6,070 views views
Watch 9 more video solutions →Practice Delete Columns to Make Sorted III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor