Delete Columns to Make Sorted II

• 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.

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.

1// This is a conceptual illustration. A direct implementation would be too slow.2// It's not practical to write runnable code for this due to its high complexity.3class Solution {4    public int minDeletionSize(String[] strs) {5        int n = strs.length;6        int m = strs[0].length();7        int minDeletions = m;8 9        // Iterate through all 2^m subsets of columns10        for (int i = 0; i < (1 << m); i++) {11            int currentDeletions = 0;12            // Build the list of columns to keep13            java.util.List<Integer> keptCols = new java.util.ArrayList<>();14            for (int j = 0; j < m; j++) {15                if ((i & (1 << j)) == 0) { // if j-th bit is 0, keep column j16                    keptCols.add(j);17                } else {18                    currentDeletions++;19                }20            }21 22            if (currentDeletions >= minDeletions) {23                continue;24            }25 26            // Check if the array is sorted with the kept columns27            if (isSorted(strs, keptCols)) {28                minDeletions = Math.min(minDeletions, currentDeletions);29            }30        }31        return minDeletions;32    }33 34    private boolean isSorted(String[] strs, java.util.List<Integer> keptCols) {35        for (int i = 0; i < strs.length - 1; i++) {36            if (compareStrings(strs[i], strs[i+1], keptCols) > 0) {37                return false;38            }39        }40        return true;41    }42 43    // Compare two strings based on a subset of columns44    private int compareStrings(String s1, String s2, java.util.List<Integer> keptCols) {45        for (int col : keptCols) {46            if (s1.charAt(col) < s2.charAt(col)) {47                return -1;48            }49            if (s1.charAt(col) > s2.charAt(col)) {50                return 1;51            }52        }53        return 0; // strings are equal54    }55}

• 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.

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.

1class Solution {2    public int minDeletionSize(String[] strs) {3        int n = strs.length;4        int m = strs[0].length();5        int deletions = 0;6 7        // sorted[i] is true if strs[i] is already lexicographically smaller than strs[i+1]8        boolean[] sorted = new boolean[n - 1];9        int sortedCount = 0; // Count of pairs that are sorted10 11        for (int j = 0; j < m; j++) {12            boolean needsDelete = false;13            // First, check if this column introduces a violation14            for (int i = 0; i < n - 1; i++) {15                // We only care about rows that are not yet sorted relative to each other16                if (!sorted[i] && strs[i].charAt(j) > strs[i+1].charAt(j)) {17                    deletions++;18                    needsDelete = true;19                    break; // This column must be deleted20                }21            }22 23            if (needsDelete) {24                continue; // Move to the next column25            }26 27            // If the column is kept, update the sorted status for newly ordered pairs28            for (int i = 0; i < n - 1; i++) {29                if (!sorted[i] && strs[i].charAt(j) < strs[i+1].charAt(j)) {30                    sorted[i] = true;31                    sortedCount++;32                }33            }34            35            // Optimization: if all pairs are sorted, we are done36            if (sortedCount == n - 1) {37                return deletions;38            }39        }40        41        return deletions;42    }43}