Delete Columns to Make Sorted III

Problem Statement

Given an array of n strings, strs, where each string has the same length, this challenge takes on the task of sorting each of these strings into lexicographic order through the process of deletion of specific character positions across all strings. Specifically, you may designate certain deletion indices and remove the corresponding characters from each string. For instance, given two strings (strs = ["abcdef","uvwxyz"]) and some deletion indices {0, 2, 3}, the resulting strings post-deletion would be ["bef", "vyz"].

The primary goal is to determine the smallest set of deletion indices ("answer") such that each string, after the character deletions, appears in a non-decreasing lexicographic order from the start to the end of the string. We need an optimal solution where the length of the set of these indices (i.e., answer.length) is minimized, while ensuring all strings remain ordered after the deletions.

Examples

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.

Approach and Intuition

To solve for the minimum number of deletions required to maintain or achieve a state where the strings in the array strs remain or become lexicographically sorted, let's evaluate the steps involved:

1. Understand the need for deletions:

   • As the strings must be individually sorted in lexicographic order post-deletion, any out-of-order character sequences within a string necessitate deletions.

2. Establish criteria for choosing deletion indices:

   • Should a character position in any string present a lexicographic inconsistency (i.e., characters are not in increasing order from one string to the next at that index), all characters in that position (column) across all strings should be considered for deletion.

3. Calculate deletions required:

   • Traverse through each character position of the strings, comparing characters of the same position across different strings:
     • If a reverse order is detected at any position in comparison between two strings, mark this position (or 'column') for deletion.

4. Compile and count the marked deletions:

   • After traversal, gather all unique indices marked for deletions and count them, as each unique index represents one necessary deletion to maintain or establish order.

5. Minimum deletions:

   • The count of unique indices required to sort all strings in lexicographic order offers the minimum necessary deletions required.

Examples as given clearly explain different scenarios:

• In example 1, deletion of columns {0, 1, 4} yields lexicographically sorted sequences.
• In example 2, almost every column must be deleted for a single string to be ordered.
• In example 3, no deletions are needed as all strings are individually sorted.

From these examples, it's evident that the effectiveness of choosing the correct deletion indices crucially depends on understanding the relationships between the positions of characters across all strings and ensuring they conform to lexicographic order.

Solutions

class Solution {
    public int minimumDeletions(String[] strs) {
        int length = strs[0].length();
        int[] count = new int[length];
        Arrays.fill(count, 1);
        for (int i = length-2; i >= 0; --i)
            iteration: for (int j = i+1; j < length; ++j) {
                for (String row : strs)
                    if (row.charAt(i) > row.charAt(j))
                        continue iteration;

                count[i] = Math.max(count[i], 1 + count[j]);
            }

        int maxKeep = 0;
        for (int val : count)
            maxKeep = Math.max(maxKeep, val);
        return length - maxKeep;
    }
}