# LeetCode 960: Delete Columns to Make Sorted III

## Problem Restatement

We are given an array `strs` of equal-length strings.

We may delete any set of column indices. When we delete a column, that position is removed from every string.

After deletions, every remaining row must be lexicographically sorted by itself:

```python
strs[row][0] <= strs[row][1] <= strs[row][2] <= ...
```

Return the minimum number of deleted columns.

Important: the array of strings does not need to be sorted. Each individual row must be sorted after deletion. This is different from LeetCode 955.

The official statement describes deleting indices from every string and requiring every final row to be lexicographically ordered.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `strs` of equal-length lowercase strings |
| Output | Minimum number of columns to delete |
| Operation | Delete the same column indices from every row |
| Requirement | Every remaining row must be nondecreasing |

Example function shape:

```python
def minDeletionSize(strs: list[str]) -> int:
    ...
```

## Examples

Example 1:

```python
strs = ["babca", "bbazb"]
```

Output:

```python
3
```

Delete columns `0`, `1`, and `4`.

The remaining rows are:

```python
"bc"
"az"
```

Both rows are individually sorted.

Example 2:

```python
strs = ["edcba"]
```

Output:

```python
4
```

With one row, we need to delete enough columns so the remaining characters are nondecreasing.

The longest sorted subsequence is any one character, so we keep `1` column and delete `4`.

Example 3:

```python
strs = ["ghi", "def", "abc"]
```

Output:

```python
0
```

Every row is already sorted, so no column must be deleted.

## First Thought: Try All Column Sets

If each string has length `m`, we could try every subset of columns to keep.

There are:

```python
2 ** m
```

possible subsets.

For each subset, we would check whether every row is sorted after keeping those columns.

This is too slow because `m` can be `100`.

## Key Insight

Instead of choosing columns to delete, choose the longest valid sequence of columns to keep.

If we can keep `L` columns, then we delete:

```python
m - L
```

So the problem becomes:

Find the longest sequence of column indices:

```python
c1 < c2 < c3 < ...
```

such that for every row:

```python
strs[row][c1] <= strs[row][c2] <= strs[row][c3] <= ...
```

This is a longest increasing subsequence style dynamic programming problem.

The difference is that one column can follow another column only if the condition holds for all rows.

## Column Compatibility

Column `prev` can come before column `cur` if:

```python
strs[row][prev] <= strs[row][cur]
```

for every row.

Example:

```python
strs = ["babca", "bbazb"]
```

Column `2` can come before column `3` if:

```python
strs[0][2] <= strs[0][3]
strs[1][2] <= strs[1][3]
```

That means:

```python
'b' <= 'c'
'a' <= 'z'
```

Both are true, so column `2` can precede column `3`.

## Algorithm

Let:

```python
m = len(strs[0])
```

Define:

```python
dp[i] = longest valid kept-column sequence ending at column i
```

Initialize every value to `1`, because any single column can be kept alone.

For every column `cur` from left to right:

1. Try every previous column `prev < cur`.
2. Check whether `prev` can come before `cur` in all rows.
3. If yes, update:

```python
dp[cur] = max(dp[cur], dp[prev] + 1)
```

After filling `dp`, the maximum number of columns we can keep is:

```python
max(dp)
```

So the answer is:

```python
m - max(dp)
```

## Correctness

We prove that the algorithm returns the minimum number of deleted columns.

A valid final result is exactly a sequence of kept columns in increasing index order. Since deleting columns preserves the original order of the remaining columns, we only need to choose which column indices stay.

For any two consecutive kept columns `prev` and `cur`, every row must satisfy:

```python
strs[row][prev] <= strs[row][cur]
```

Otherwise, that row would decrease at this adjacent kept-column pair, so the final row would not be sorted.

The dynamic programming state `dp[cur]` stores the longest valid kept-column sequence that ends at `cur`.

The initialization `dp[cur] = 1` is correct because a single column is always valid.

For each earlier column `prev`, if `prev` can legally precede `cur` in every row, then any valid sequence ending at `prev` can be extended by `cur`. This gives a candidate length `dp[prev] + 1`.

If `prev` cannot precede `cur`, then no valid sorted row sequence can place `cur` immediately after `prev`, so that transition is correctly rejected.

Thus every valid kept-column sequence is considered by the DP, and every DP transition creates a valid kept-column sequence. Therefore, `max(dp)` is the maximum number of columns that can be kept.

Since every column is either kept or deleted, minimizing deletions is the same as maximizing kept columns. The answer is `m - max(dp)`.

## Complexity

Let:

```python
n = len(strs)
m = len(strs[0])
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * m^2)` | For each pair of columns, check all rows |
| Space | `O(m)` | The DP array stores one value per column |

The official constraints allow `n <= 100` and `m <= 100`, so this is efficient.

## Implementation

```python
class Solution:
    def minDeletionSize(self, strs: list[str]) -> int:
        m = len(strs[0])
        dp = [1] * m

        for cur in range(m):
            for prev in range(cur):
                can_follow = True

                for row in strs:
                    if row[prev] > row[cur]:
                        can_follow = False
                        break

                if can_follow:
                    dp[cur] = max(dp[cur], dp[prev] + 1)

        return m - max(dp)
```

## Code Explanation

We start with:

```python
m = len(strs[0])
dp = [1] * m
```

Each column can form a valid kept sequence by itself.

Then we try to end a sequence at every column:

```python
for cur in range(m):
```

For each `cur`, we test all previous columns:

```python
for prev in range(cur):
```

Now we check whether `prev` can come before `cur` for every row:

```python
for row in strs:
    if row[prev] > row[cur]:
        can_follow = False
        break
```

If any row decreases, this transition is invalid.

If all rows pass, we extend the best sequence ending at `prev`:

```python
dp[cur] = max(dp[cur], dp[prev] + 1)
```

Finally:

```python
return m - max(dp)
```

The maximum value in `dp` is the most columns we can keep. The rest must be deleted.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minDeletionSize(["babca", "bbazb"]) == 3
    assert s.minDeletionSize(["edcba"]) == 4
    assert s.minDeletionSize(["ghi", "def", "abc"]) == 0

    assert s.minDeletionSize(["abc"]) == 0
    assert s.minDeletionSize(["cba"]) == 2
    assert s.minDeletionSize(["aaa", "aaa"]) == 0
    assert s.minDeletionSize(["zyx", "wvu", "tsr"]) == 2
    assert s.minDeletionSize(["abcdef", "uvwxyz"]) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `["babca","bbazb"]` | Official-style example with shared deletion set |
| `["edcba"]` | Single decreasing row |
| `["ghi","def","abc"]` | Rows already sorted |
| `["abc"]` | Single sorted row |
| `["cba"]` | Single-row LIS behavior |
| Equal rows | Nondecreasing allows equality |
| All rows decreasing | Can keep only one column |
| Two increasing rows | No deletion needed |