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.In #960 Delete Columns to Make Sorted III, we must remove the minimum number of columns so that the remaining columns keep every row in non-decreasing order. Instead of greedily deleting columns, the key insight is to view the columns as a sequence and determine the maximum number of columns we can keep.
This can be modeled as a variation of the Longest Increasing Subsequence (LIS) across columns. For two columns i and j (where i < j), column j can follow column i only if for every row r, the condition A[r][i] <= A[r][j] holds. Using dynamic programming, we compute the longest valid chain of columns satisfying this rule.
Let dp[j] represent the maximum number of valid columns ending at column j. We iterate through previous columns to update it. The answer is the total columns minus the longest valid sequence we can keep. This approach efficiently captures the global ordering constraint across all rows.
Time Complexity: O(n² × m), where n is the number of columns and m is the number of rows. Space Complexity: O(n).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (LIS-style on columns) | O(n^2 * m) | O(n) |
Varun Gupta
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4int minDeletionSize(char** strs, int strsSize) {
5 int n
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.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems with similar patterns frequently appear in FAANG-style interviews. This question tests dynamic programming, sequence optimization, and recognizing LIS-style transformations, which are common interview themes.
The optimal strategy uses dynamic programming inspired by the Longest Increasing Subsequence. We treat columns as elements in a sequence and check whether one column can follow another by ensuring all rows remain non-decreasing. The result is the number of columns minus the longest valid column chain.
Dynamic programming helps track the longest valid sequence of columns that maintain sorted order across every row. Since each column decision depends on earlier columns, DP efficiently evaluates all possible transitions while avoiding repeated checks.
A simple DP array is sufficient for this problem. It stores the maximum valid subsequence length ending at each column while iterating through previous columns and verifying the ordering condition across all rows.
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.