Leetcode 960. Delete Columns to Make Sorted III

Let's understand what we're being asked to do. We have n strings of equal length, like ['abc', 'bce', 'cae']. Each string is a row, and we can think of columns as vertical slices: column 0 is 'a', 'b', 'c', column 1 is 'b', 'c', 'a', column 2 is 'c', 'e', 'e'.

We need to delete the minimum number of columns so that in every remaining row, the characters are in non-decreasing order (sorted). For example, if we keep columns 0 and 2, row 0 becomes 'ac' (sorted ✓), row 1 becomes 'be' (sorted ✓), row 2 becomes 'ce' (sorted ✓).

Key constraint: We must ensure ALL rows are sorted after deletion. If even one row is unsorted, that column set doesn't work.

Edge cases to consider: What if all columns must be deleted? What if no columns need deletion (already sorted)? What if n=1 (single string - any column subset works)?

The brute force approach would enumerate all possible subsets of columns (there are 2^m subsets where m is the number of columns). For each subset, check if keeping those columns makes every row sorted. Track the maximum size of a valid subset found. This approach is simple to understand but exponential in time complexity, making it impractical for even moderate input sizes.

def min_deletion_size(strs):
    """
    Brute force: Try all 2^m subsets of columns.
    For each subset, check if keeping those columns makes every row sorted.
    Return m minus the maximum valid subset size.
    """
    if not strs:
        return 0
    
    n = len(strs)
    m = len(strs[0])
    max_valid_columns = 0
    
    # Try all 2^m subsets using bitmask
    for mask in range(1 << m):
        # Extract columns corresponding to set bits in mask
        selected_columns = []
        for col in range(m):
            if mask & (1 << col):
                selected_columns.append(col)
        
        # Check if this subset keeps all rows sorted
        is_valid = True
        for row_idx in range(n):
            # Build the string for this row using selected columns
            row_chars = []
            for col in selected_columns:
                row_chars.append(strs[row_idx][col])
            
            # Check if this row's characters are non-decreasing
            for i in range(len(row_chars) - 1):
                if row_chars[i] > row_chars[i + 1]:
                    is_valid = False
                    break
            
            if not is_valid:
                break
        
        # Update maximum valid subset size
        if is_valid:
            max_valid_columns = max(max_valid_columns, len(selected_columns))
    
    # Return number of columns to delete
    return m - max_valid_columns

This problem is asking us to find the longest sequence of column indices such that keeping those columns makes every row sorted.

If we can find the longest valid sequence of length L, then we need to delete m - L columns (where m is the total number of columns). The key insight is that a valid sequence of columns must be non-decreasing in every row simultaneously.

Instead of trying all possible column subsets (which would be exponential), we can use dynamic programming to build up valid sequences incrementally.

For each column, we ask: 'Can I extend any previous valid sequence by adding this column?' This transforms an exponential search into a polynomial-time solution by reusing previously computed results.

Think of this like building a chain of columns. You start with individual columns (chains of length 1). Then you try to extend each chain by adding a new column - but you can only add column j to a chain ending at column i if:

1. Column j comes after column i (index-wise)
2. For every row, the character in column j is >= the character in column i

This 'building longer chains from shorter ones' pattern is the essence of dynamic programming on sequences.

The optimal approach uses dynamic programming similar to the Longest Increasing Subsequence (LIS) problem. For each column j, we compute dp[j] = the length of the longest valid column sequence ending at column j. We can extend a sequence ending at column i to column j if j > i and for every row, strs[row][j] >= strs[row][i]. The answer is m - max(dp), where max(dp) is the longest valid sequence we can keep.

def min_deletion_size(strs):
    """
    Find minimum number of columns to delete so remaining characters
    in each row are non-decreasing. Uses DP similar to LIS.
    """
    if not strs or not strs[0]:
        return 0
    
    n = len(strs)
    m = len(strs[0])
    
    # dp[j] = length of longest valid column sequence ending at column j
    dp = [1] * m
    
    # For each column j
    for j in range(m):
        # Try to extend from each previous column i
        for i in range(j):
            # Check if we can extend sequence from i to j
            can_extend = True
            for row in range(n):
                if strs[row][j] < strs[row][i]:
                    can_extend = False
                    break
            
            # If valid, update dp[j]
            if can_extend:
                dp[j] = max(dp[j], dp[i] + 1)
    
    # Find maximum length sequence we can keep
    max_keep = max(dp)
    
    # Return columns to delete
    return m - max_keep

• Dynamic Programming on column indices: This problem transforms a 2D constraint (all rows must be non-decreasing) into a 1D DP problem by treating columns as elements - use DP[i] to represent the longest valid sequence ending at column i, where validity means all rows satisfy the non-decreasing property between selected columns.
• Longest Increasing Subsequence (LIS) variant recognition: When asked to delete minimum elements to satisfy an ordering constraint, reframe it as finding the maximum elements you can keep - this converts 'minimum deletions' to 'maximum valid subsequence length' where answer = total - max_kept.
• Multi-row validation pattern: For each potential column pair (j, i), you must validate the constraint across ALL rows simultaneously - use a helper function that checks if column j can precede column i by iterating through every row and ensuring s[row][j] <= s[row][i] for all rows.
• Quadratic DP transition optimization: The O(m²) column comparison is unavoidable when each column depends on all previous columns, but optimize by breaking early in validation loops - if any single row violates the non-decreasing property between two columns, immediately return false without checking remaining rows.
• Column-wise thinking for string arrays: When dealing with arrays of equal-length strings where operations affect entire columns, mentally transpose the problem - think of columns as independent units and rows as constraints that must all be satisfied, rather than processing strings individually.
• Greedy won't work insight: You cannot greedily select columns left-to-right because a locally valid choice might block better global solutions - DP is necessary because the optimal subsequence of columns requires considering all possible previous columns at each step, similar to classic LIS where order matters but selection is flexible.