Scale Engineer

Delete Columns to Make Sorted III

Hard
#0914Time: 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.
Patterns
Dynamic Programming
Data structures
ArrayString

Prompt

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.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 100
  • strs[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 from currCol, given the last included column was prevCol.
  • The base case for the recursion is when currCol equals the total number of columns (L), in which case it returns 0.
  • In the recursive step, consider two choices for currCol:
    1. Exclude currCol: Recursively call findMaxLen(prevCol, currCol + 1).
    2. Include currCol: This is only possible if currCol is compatible with prevCol. If prevCol is -1 (start of sequence) or for all rows r, strs[r][currCol] >= strs[r][prevCol], then it's compatible. The length would be 1 + findMaxLen(currCol, currCol + 1).
  • 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:

  1. 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).
  2. Include the column: We can only include currCol if it maintains the sorted property with respect to prevCol. This means for every string in strs, the character at currCol must be greater than or equal to the character at prevCol. If this condition holds, we include the column, and the length becomes 1 + 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

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.

← Previous

Previous problem

Next →

Next problem