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.length1 <= n <= 1001 <= strs[i].length <= 100strs[i] consists of lowercase English letters.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force method for this problem is all about trying every possible combination of column deletions to find one that works. We systematically check each possibility, even if it takes a very long time. We'll explore every combination of columns we can delete and see if the remaining ones make the rows sorted.
Here's how the algorithm would work step-by-step:
def delete_columns_to_make_sorted_brute_force(strings):
number_of_strings = len(strings)
if number_of_strings <= 1:
return 0
string_length = len(strings[0])
minimum_deleted_columns = string_length
for i in range(1 << string_length):
deleted_columns_count = 0
columns_to_keep = []
for column_index in range(string_length):
if (i >> column_index) & 1:
deleted_columns_count += 1
else:
columns_to_keep.append(column_index)
is_sorted = True
# Iterate to see if the string is sorted after deleting columns.
for string_index in range(1, number_of_strings):
previous_string = ""
current_string = ""
for column_index in columns_to_keep:
previous_string += strings[string_index - 1][column_index]
current_string += strings[string_index][column_index]
if previous_string > current_string:
is_sorted = False
break
# If the column removal yields a sorted result.
if is_sorted:
minimum_deleted_columns = min(minimum_deleted_columns, deleted_columns_count)
return minimum_deleted_columnsThe core idea is to efficiently identify and eliminate columns that would disrupt the sorted order of rows. We achieve this by iteratively checking rows and intelligently tracking which rows are already sorted, avoiding unnecessary comparisons and deletions.
Here's how the algorithm would work step-by-step:
def min_deletion_size(strs):
number_of_rows = len(strs)
number_of_columns = len(strs[0])
deleted_column_count = 0
sorted_rows = [False] * number_of_rows
for column_index in range(number_of_columns):
currently_sorted = sorted_rows[:]
for row_index in range(1, number_of_rows):
# Only check unsorted rows.
if not sorted_rows[row_index]:
if strs[row_index][column_index] < strs[row_index - 1][column_index]:
deleted_column_count += 1
break
# Rows are sorted if current char is equal
elif strs[row_index][column_index] > strs[row_index - 1][column_index]:
currently_sorted[row_index] = True
else:
# This column didn't need to be deleted, update sorted rows.
# Need to update sorted rows only if no column deletion occurred
sorted_rows = currently_sorted
return deleted_column_count| Case | How to Handle |
|---|---|
| Empty input array | Return 0, as no columns need to be deleted in an empty array. |
| Array with only one string | Return 0, as a single string is always considered sorted. |
| Strings with different lengths | The algorithm must handle strings of unequal length by stopping comparison at the shortest string's length and continuing processing. |
| Array with strings of maximum allowed length (or close to it) | Ensure algorithm efficiency prevents excessive memory usage or runtime, especially when many strings are close to maximum length. |
| All strings are identical | Return 0, as no columns need to be deleted if all strings are the same. |
| All strings are sorted lexicographically | Return 0, as no columns need to be deleted because the array is already sorted. |
| Strings with non-ASCII characters (Unicode) | Ensure the character comparison logic correctly handles Unicode characters based on their lexicographical order. |
| Very large input array size | The algorithm should be optimized for space and time to handle arrays containing a large number of strings efficiently, potentially needing to avoid quadratic complexities. |