Delete Columns to Make Sorted III
HardPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach attempts to solve the problem by exploring all possible subsequences of columns. It uses a recursive function to generate and check these subsequences. At each column, it decides whether to include it in the subsequence or not, leading to an exponential number of possibilities.
Algorithm
- Define a recursive function
findMaxLen(prevCol, currCol)that returns the length of the longest valid subsequence of columns starting fromcurrCol, given the last included column wasprevCol. - The base case for the recursion is when
currColequals the total number of columns (L), in which case it returns 0. - In the recursive step, consider two choices for
currCol:- Exclude
currCol: Recursively callfindMaxLen(prevCol, currCol + 1). - Include
currCol: This is only possible ifcurrColis compatible withprevCol. IfprevColis -1 (start of sequence) or for all rowsr,strs[r][currCol] >= strs[r][prevCol], then it's compatible. The length would be1 + findMaxLen(currCol, currCol + 1).
- Exclude
- The function returns the maximum length from the valid choices.
- The initial call is
findMaxLen(-1, 0). - The final result is
L - findMaxLen(-1, 0).
Walkthrough
The problem asks for the minimum number of columns to delete, which is equivalent to finding the maximum number of columns to keep. This approach uses a brute-force recursive method to find the length of the longest subsequence of columns that satisfies the non-decreasing condition for every row.
A recursive function, let's call it findMaxLen(prevCol, currCol), is defined. prevCol is the index of the last column added to our subsequence, and currCol is the column we are currently considering.
For each currCol, we explore two possibilities:
- Exclude the column: We simply skip this column and move to the next one. The length of the subsequence in this case is determined by
findMaxLen(prevCol, currCol + 1). - Include the column: We can only include
currColif it maintains the sorted property with respect toprevCol. This means for every string instrs, the character atcurrColmust be greater than or equal to the character atprevCol. If this condition holds, we include the column, and the length becomes1 + findMaxLen(currCol, currCol + 1).
The function returns the maximum of the lengths obtained from these two choices. The recursion stops when currCol goes beyond the last column index, returning 0. The main function calls findMaxLen(-1, 0) to start the process and then subtracts the result from the total number of columns to get the minimum deletions.
class Solution { int n; int l; String[] strs; public int minDeletionSize(String[] strs) { this.n = strs.length; this.l = strs[0].length(); this.strs = strs; int maxLen = findMaxLen(-1, 0); return l - maxLen; } private int findMaxLen(int prevCol, int currCol) { if (currCol == l) { return 0; } // Option 1: Exclude currCol int len1 = findMaxLen(prevCol, currCol + 1); // Option 2: Include currCol boolean isCompatible = true; if (prevCol != -1) { for (int i = 0; i < n; i++) { if (strs[i].charAt(currCol) < strs[i].charAt(prevCol)) { isCompatible = false; break; } } } int len2 = 0; if (isCompatible) { len2 = 1 + findMaxLen(currCol, currCol + 1); } return Math.max(len1, len2); }}Complexity
Time
O(2^L * N), where L is the length of the strings and N is the number of strings. For each of the `L` columns, we have two choices (include or exclude), leading to `2^L` possibilities. The compatibility check takes O(N).
Space
O(L), where L is the length of the strings. This is for the recursion call stack depth.
Trade-offs
Pros
Conceptually simple and follows a straightforward divide-and-conquer logic.
Cons
Extremely inefficient due to re-computation of overlapping subproblems.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
Solutions
Solution
class Solution { public int minDeletionSize ( String [] strs ) { int n = strs [ 0 ]. length (); int [] dp = new int [ n ]; Arrays . fill ( dp , 1 ); int mx = 1 ; for ( int i = 1 ; i < n ; ++ i ) { for ( int j = 0 ; j < i ; ++ j ) { if ( check ( i , j , strs )) { dp [ i ] = Math . max ( dp [ i ], dp [ j ] + 1 ); } } mx = Math . max ( mx , dp [ i ]); } return n - mx ; } private boolean check ( int i , int j , String [] strs ) { for ( String s : strs ) { if ( s . charAt ( i ) < s . charAt ( j )) { return false ; } } return true ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.