# Delete Columns to Make Sorted II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/delete-columns-to-make-sorted-ii)
Canonical: https://scaleengineer.com/dsa/problems/delete-columns-to-make-sorted-ii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**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 its elements in **lexicographic** order (i.e., `strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]`). Return _the minimum possible value of_ `answer.length`.

**Example 1:**

**Input:** strs = ["ca","bb","ac"]
**Output:** 1
**Explanation:** 
After deleting the first column, strs = ["a", "b", "c"].
Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]).
We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.

**Example 2:**

**Input:** strs = ["xc","yb","za"]
**Output:** 0
**Explanation:** 
strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= ...)

**Example 3:**

**Input:** strs = ["zyx","wvu","tsr"]
**Output:** 3
**Explanation:** We have to delete every column.

**Constraints:**

* `n == strs.length`
* `1 <= n <= 100`
* `1 <= strs[i].length <= 100`
* `strs[i]` consists of lowercase English letters.

# Approaches
## Brute Force by Checking All Deletion Subsets
This approach exhaustively checks every possible subset of columns to delete. For each subset, it constructs the resulting strings and verifies if they are in lexicographical order. The goal is to find the smallest subset of deletions that satisfies the condition.
**Time:** O(2^M * N * M), where `N` is the number of strings and `M` is the length of each string. This is because there are `2^M` subsets of columns, and for each, we perform a check that takes O(N * M) time in the worst case. · **Space:** O(M) to store the indices of the columns to be kept for each subset. The check can be done without creating new strings.
**Pros:** Guaranteed to find the optimal solution because it checks every possibility.
**Cons:** Extremely inefficient with a time complexity that is exponential in the number of columns.; Impractical for the given constraints (`M` up to 100).
### Explanation
The algorithm iterates through all `2^M` possible subsets of columns, where `M` is the number of columns. Each subset represents a potential set of columns to delete. A bitmask is a convenient way to represent these subsets, where the `j`-th bit being 1 means column `j` is deleted.
For each subset:
1. We determine the number of columns to be deleted (the number of set bits in the mask).
2. We then check if the remaining columns make the array of strings lexicographically sorted. This is done by comparing each adjacent pair of strings, `strs[i]` and `strs[i+1]`, considering only the characters in the non-deleted columns.
3. If `strs[i]` (with non-deleted columns) is found to be greater than `strs[i+1]` (with non-deleted columns) for any `i`, this subset is invalid, and we move to the next subset.
4. If all pairs are correctly ordered, the subset is valid. We then update our answer with the current number of deletions if it's smaller than the minimum found so far.
This process continues until all `2^M` subsets have been checked.
```java
// This is a conceptual illustration. A direct implementation would be too slow.
// It's not practical to write runnable code for this due to its high complexity.
class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        int minDeletions = m;

        // Iterate through all 2^m subsets of columns
        for (int i = 0; i < (1 << m); i++) {
            int currentDeletions = 0;
            // Build the list of columns to keep
            java.util.List<Integer> keptCols = new java.util.ArrayList<>();
            for (int j = 0; j < m; j++) {
                if ((i & (1 << j)) == 0) { // if j-th bit is 0, keep column j
                    keptCols.add(j);
                } else {
                    currentDeletions++;
                }
            }

            if (currentDeletions >= minDeletions) {
                continue;
            }

            // Check if the array is sorted with the kept columns
            if (isSorted(strs, keptCols)) {
                minDeletions = Math.min(minDeletions, currentDeletions);
            }
        }
        return minDeletions;
    }

    private boolean isSorted(String[] strs, java.util.List<Integer> keptCols) {
        for (int i = 0; i < strs.length - 1; i++) {
            if (compareStrings(strs[i], strs[i+1], keptCols) > 0) {
                return false;
            }
        }
        return true;
    }

    // Compare two strings based on a subset of columns
    private int compareStrings(String s1, String s2, java.util.List<Integer> keptCols) {
        for (int col : keptCols) {
            if (s1.charAt(col) < s2.charAt(col)) {
                return -1;
            }
            if (s1.charAt(col) > s2.charAt(col)) {
                return 1;
            }
        }
        return 0; // strings are equal
    }
}
```
### Algorithm
- Initialize `min_deletions` to `M` (number of columns).
- Generate all `2^M` subsets of column indices. A bitmask from `0` to `2^M - 1` can be used.
- For each subset (mask):
  - Count the number of deleted columns (number of set bits in the mask).
  - If this count is already greater than or equal to `min_deletions`, skip to the next subset.
  - Check if the array is sorted using only the columns that are *not* in the deletion set.
  - To check, iterate through adjacent rows `i` from `0` to `N-2`:
    - Compare `strs[i]` and `strs[i+1]` using only the kept columns.
    - If `strs[i]` > `strs[i+1]`, the order is violated. This subset is invalid. Break and check the next subset.
  - If the check completes without violations, this subset is valid. Update `min_deletions = min(min_deletions, current_deletions)`.
- Return `min_deletions`.

## Greedy Column-by-Column Check
This efficient approach iterates through the columns from left to right, making a greedy decision for each one. It keeps a column if and only if it does not create a lexicographical disorder (`strs[i] > strs[i+1]`) among rows that are currently considered tied. This works because columns are processed in order of their significance in lexicographical comparison.
**Time:** O(N * M), where `N` is the number of strings and `M` is the length of each string. We iterate through each column, and for each column, we iterate through all adjacent rows. · **Space:** O(N) to store the `sorted` status for the `N-1` adjacent pairs of strings.
**Pros:** Very efficient with a linear time complexity relative to the input size.; Simple to implement.; Correctly finds the minimum number of deletions due to the nature of lexicographical ordering.
**Cons:** Requires extra space for the `sorted` array.
### Explanation
The intuition behind the greedy strategy is that we want to minimize deletions, which is the same as maximizing the number of columns we keep. When comparing strings lexicographically, leftmost characters are most important. So, we should prioritize keeping columns from the left.

We process columns one by one, from `j = 0` to `M-1`. We maintain a boolean array, `sorted`, of size `N-1`. `sorted[i]` becomes `true` once we have established that `strs[i]` is lexicographically smaller than `strs[i+1]` based on the columns we've kept so far. Initially, all entries in `sorted` are `false`, as all adjacent strings are considered 'tied'.

For each column `j`:
1. We first check if keeping this column would create an invalid ordering. We iterate through adjacent rows `i` from `0` to `N-2`. If `sorted[i]` is `false` (the pair `(strs[i], strs[i+1])` is still tied) and `strs[i][j] > strs[i+1][j]`, then keeping this column would make `strs[i]` greater than `strs[i+1]`. This cannot be undone by any subsequent columns. Thus, we *must* delete column `j`. We increment our deletion counter and move to the next column.

2. If the column passes this check (i.e., it doesn't create any `>` relationships for tied rows), we decide to keep it. Now, we update the `sorted` array. For any pair `i` where `sorted[i]` was `false` and `strs[i][j] < strs[i+1][j]`, the order is now resolved. We set `sorted[i]` to `true`.

As an optimization, if all entries in the `sorted` array become `true`, it means the entire list of strings is lexicographically sorted. We can stop processing further columns and return the current deletion count.

```java
class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        int deletions = 0;

        // sorted[i] is true if strs[i] is already lexicographically smaller than strs[i+1]
        boolean[] sorted = new boolean[n - 1];
        int sortedCount = 0; // Count of pairs that are sorted

        for (int j = 0; j < m; j++) {
            boolean needsDelete = false;
            // First, check if this column introduces a violation
            for (int i = 0; i < n - 1; i++) {
                // We only care about rows that are not yet sorted relative to each other
                if (!sorted[i] && strs[i].charAt(j) > strs[i+1].charAt(j)) {
                    deletions++;
                    needsDelete = true;
                    break; // This column must be deleted
                }
            }

            if (needsDelete) {
                continue; // Move to the next column
            }

            // If the column is kept, update the sorted status for newly ordered pairs
            for (int i = 0; i < n - 1; i++) {
                if (!sorted[i] && strs[i].charAt(j) < strs[i+1].charAt(j)) {
                    sorted[i] = true;
                    sortedCount++;
                }
            }
            
            // Optimization: if all pairs are sorted, we are done
            if (sortedCount == n - 1) {
                return deletions;
            }
        }
        
        return deletions;
    }
}
```
### Algorithm
- Initialize `deletions = 0`.
- Initialize a boolean array `sorted` of size `N-1` to all `false`. `sorted[i]` will be true if `strs[i] < strs[i+1]` is established.
- Iterate through each column `j` from `0` to `M-1`:
  - Assume the column will be kept. Check for violations by iterating through adjacent rows `i` from `0` to `N-2`:
    - If `sorted[i]` is `false` and `strs[i].charAt(j) > strs[i+1].charAt(j)`, a violation occurs.
    - In case of a violation, increment `deletions`, mark this column for deletion, and break the inner loop (over `i`).
  - If the column was marked for deletion, `continue` to the next column `j+1`.
  - If the column is kept, update the `sorted` array. Iterate through rows `i` from `0` to `N-2`:
    - If `sorted[i]` is `false` and `strs[i].charAt(j) < strs[i+1].charAt(j)`, set `sorted[i]` to `true`.
  - If all elements in `sorted` are `true`, break the main loop and return `deletions`.
- Return `deletions`.

# Solutions
### Java

```java
class Solution {
public
  int minDeletionSize(String[] A) {
    if (A == null || A.length <= 1) {
      return 0;
    }
    int len = A.length, wordLen = A[0].length(), res = 0;
    boolean[] cut = new boolean[len];
  search:
    for (int j = 0; j < wordLen; j++) {
```