# Delete Columns to Make Sorted III
**Difficulty:** HARD
[External](https://leetcode.com/problems/delete-columns-to-make-sorted-iii)
Canonical: https://scaleengineer.com/dsa/problems/delete-columns-to-make-sorted-iii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, String
---
## Problem
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
## Brute-Force Recursion
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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### 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)`.

## Top-Down Dynamic Programming (Memoization)
This approach optimizes the brute-force recursion by using memoization, a technique also known as top-down dynamic programming. It avoids re-calculating results for the same subproblems by storing them in a cache (a 2D array). This turns the exponential complexity into a polynomial one.
**Time:** O(L^2 * N), where L is the length of the strings and N is the number of strings. There are `O(L^2)` states, and each state computation involves a compatibility check taking O(N) time. · **Space:** O(L^2), where L is the length of the strings. This is for the `(L+1) x L` memoization table. The recursion stack also adds O(L).
**Pros:** Significantly more efficient than brute-force.; Guaranteed to solve the problem within the time limits.; The logic closely follows the recursive thought process, which can be intuitive.
**Cons:** Requires more space than the bottom-up DP approach due to the 2D memoization table.
### Explanation
The brute-force recursive solution suffers from solving the same subproblems multiple times. A subproblem is uniquely identified by the state `(prevCol, currCol)`. We can optimize this by storing the result of each subproblem in a memoization table.

We create a 2D array, `memo`, of size `(L+1) x L`. `memo[prevCol + 1][currCol]` will store the result of `findMaxLen(prevCol, currCol)`. We add 1 to `prevCol` to handle the initial case where `prevCol` is -1.

Inside the recursive function, before any computation, we check if the result for the current state `(prevCol, currCol)` is already stored in our `memo` table. If it is, we return the stored value directly. Otherwise, we proceed with the computation as in the brute-force method. Once the result is computed, we store it in the `memo` table before returning. This ensures that each of the `O(L^2)` possible states is computed only once.

```java
class Solution {
    int n;
    int l;
    String[] strs;
    Integer[][] memo;

    public int minDeletionSize(String[] strs) {
        this.n = strs.length;
        this.l = strs[0].length();
        this.strs = strs;
        this.memo = new Integer[l + 1][l];
        
        int maxLen = findMaxLen(-1, 0);
        return l - maxLen;
    }

    private int findMaxLen(int prevCol, int currCol) {
        if (currCol == l) {
            return 0;
        }
        
        if (memo[prevCol + 1][currCol] != null) {
            return memo[prevCol + 1][currCol];
        }

        // 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);
        }

        int result = Math.max(len1, len2);
        memo[prevCol + 1][currCol] = result;
        return result;
    }
}
```
### Algorithm
- Use the same recursive structure as the brute-force approach: `findMaxLen(prevCol, currCol)`.
- Introduce a 2D memoization table, `memo[L+1][L]`, initialized with a value indicating 'not computed' (e.g., null).
- Before any computation in `findMaxLen`, check if `memo[prevCol+1][currCol]` has a stored value. If yes, return it immediately.
- If the value is not in the memo table, perform the recursive calculations as in the brute-force approach.
- Store the computed result in `memo[prevCol+1][currCol]` before returning it.
- The rest of the logic remains the same.

## Bottom-Up Dynamic Programming
This is the most efficient approach, utilizing bottom-up dynamic programming. The problem is modeled as finding the Longest Increasing Subsequence (LIS), where the 'elements' are the columns and the 'increasing' condition is that a column can follow another if it maintains the lexicographical order for all rows. This approach iteratively builds the solution using a 1D DP array, offering the best space complexity.
**Time:** O(L^2 * N), where L is the length of the strings and N is the number of strings. The nested loops run in `O(L^2)`, and the compatibility check inside takes O(N). · **Space:** O(L), where L is the length of the strings. This is for the 1D `dp` array.
**Pros:** Most space-efficient solution.; Efficient time complexity suitable for the given constraints.; It's an iterative solution, avoiding potential recursion depth issues.
**Cons:** The LIS-based formulation might be less intuitive to derive compared to a direct recursive approach.
### Explanation
The problem of finding the maximum number of columns to keep can be perfectly mapped to the classic Longest Increasing Subsequence (LIS) problem. Here, the sequence is the columns from index 0 to `L-1`.

We define `dp[i]` as the length of the longest valid subsequence of columns that ends with column `i`.

1.  Initialize a 1D array `dp` of size `L` (the number of columns) and fill it with 1s. This is because every column by itself forms a valid subsequence of length 1.
2.  We iterate through the columns from `i = 0` to `L-1`.
3.  For each column `i`, we look back at all previous columns `j` (where `0 <= j < i`).
4.  We check if column `i` can extend a subsequence that ends at `j`. The condition for this is that column `i` must be 'greater than or equal to' column `j`. In this problem's context, this means for every row `k`, `strs[k].charAt(i) >= strs[k].charAt(j)`.
5.  If this compatibility condition is met, it means we can append column `i` to the subsequence ending at `j`. The new length would be `dp[j] + 1`. We want the longest possible subsequence ending at `i`, so we update `dp[i]` using the formula: `dp[i] = Math.max(dp[i], 1 + dp[j])`.
6.  After the loops complete, the `dp` array is filled. The maximum value in this array represents the length of the longest valid subsequence of columns we can keep.
7.  The minimum number of deletions is the total number of columns `L` minus this maximum length.

```java
import java.util.Arrays;

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int l = strs[0].length();
        int[] dp = new int[l];
        Arrays.fill(dp, 1);
        int maxLen = 1;

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < i; j++) {
                boolean isCompatible = true;
                for (int k = 0; k < n; k++) {
                    if (strs[k].charAt(i) < strs[k].charAt(j)) {
                        isCompatible = false;
                        break;
                    }
                }
                if (isCompatible) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return l - maxLen;
    }
}
```
### Algorithm
- Rephrase the problem as finding the Longest Increasing Subsequence (LIS) of columns.
- Create a DP array `dp` of size `L`, where `dp[i]` stores the length of the longest valid subsequence of columns ending at index `i`.
- Initialize all elements of `dp` to 1, as any single column is a valid subsequence of length 1.
- Iterate with `i` from 0 to `L-1` (for each column).
  - Inside, iterate with `j` from 0 to `i-1` (for each previous column).
  - Check if column `i` can follow column `j`. This is true if for all rows `r`, `strs[r][j] <= strs[r][i]`.
  - If they are compatible, update `dp[i] = max(dp[i], 1 + dp[j])`.
- Keep track of the maximum value found in the `dp` array. This will be the maximum number of columns we can keep (`maxLen`).
- The final answer is `L - maxLen`.

# Solutions
### Java

```java
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 ; } }
```

### Python

```python
class Solution : def minDeletionSize ( self , strs : List [ str ]) -> int : n = len ( strs [ 0 ]) dp = [ 1 ] * n for i in range ( 1 , n ): for j in range ( i ): if all ( s [ j ] <= s [ i ] for s in strs ): dp [ i ] = max ( dp [ i ], dp [ j ] + 1 ) return n - max ( dp )
```

### CPP

```cpp
class Solution { public: int minDeletionSize ( vector < string >& strs ) { int n = strs [ 0 ]. size (); vector < int > dp ( n , 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 ] = max ( dp [ i ], dp [ j ] + 1 ); } } mx = max ( mx , dp [ i ]); } return n - mx ; } bool check ( int i , int j , vector < string >& strs ) { for ( string & s : strs ) if ( s [ i ] < s [ j ]) return false ; return true ; } };
```