You are given an array of n strings strs, all of the same length.
The strings can be arranged such that there is one on each line, making a grid.
strs = ["abc", "bce", "cae"] can be arranged as follows:abc bce cae
You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.
Return the number of columns that you will delete.
Example 1:
Input: strs = ["cba","daf","ghi"] Output: 1 Explanation: The grid looks as follows: cba daf ghi Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.
Example 2:
Input: strs = ["a","b"] Output: 0 Explanation: The grid looks as follows: a b Column 0 is the only column and is sorted, so you will not delete any columns.
Example 3:
Input: strs = ["zyx","wvu","tsr"] Output: 3 Explanation: The grid looks as follows: zyx wvu tsr All 3 columns are not sorted, so you will delete all 3.
Constraints:
n == strs.length1 <= n <= 1001 <= strs[i].length <= 1000strs[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:
Imagine you have a list of words stacked on top of each other. The goal is to find the fewest number of columns to remove so that the words are sorted alphabetically when read from top to bottom. The brute force method tries out all possible combinations of columns to remove.
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_columns_to_remove = string_length
for i in range(1 << string_length):
columns_to_keep = []
columns_to_remove_count = 0
for column_index in range(string_length):
if (i >> column_index) & 1:
columns_to_keep.append(column_index)
else:
columns_to_remove_count += 1
is_sorted = True
# Construct strings with only the kept columns
modified_strings = []
for string in strings:
modified_string = ''
for column_index in columns_to_keep:
modified_string += string[column_index]
modified_strings.append(modified_string)
# Check if the strings are sorted
for string_index in range(number_of_strings - 1):
if modified_strings[string_index] > modified_strings[string_index + 1]:
is_sorted = False
break
if is_sorted:
# Update the minimum number of columns to remove
minimum_columns_to_remove = min(minimum_columns_to_remove, columns_to_remove_count)
return minimum_columns_to_removeThe key is to examine the input column by column. If a column disrupts the sorted order of the rows, we count it for deletion. We only need to focus on adjacent rows to determine if a column creates an out-of-order situation.
Here's how the algorithm would work step-by-step:
def delete_columns_to_make_sorted(strings):
number_of_columns_to_delete = 0
number_of_columns = len(strings[0])
for column_index in range(number_of_columns):
# Check each column to determine if it needs to be deleted.
for row_index in range(len(strings) - 1):
# Compare current row with the next row
if strings[row_index][column_index] > strings[row_index + 1][column_index]:
# Found a column that needs to be deleted.
number_of_columns_to_delete += 1
break
return number_of_columns_to_delete| Case | How to Handle |
|---|---|
| Null or empty input array | Return 0 as there are no columns to potentially delete. |
| Array containing an empty string | Treat the empty string as the smallest possible string and compare appropriately. |
| Array with only one string | Return 0 as a single string is always sorted. |
| Strings of significantly varying lengths | Iterate only up to the length of the shortest string, safely ignoring the longer strings' extra characters. |
| Strings with all the same characters | The solution should correctly identify these columns as sorted and not delete them. |
| Input array with a very large number of strings | Ensure the solution uses a reasonably space-efficient algorithm, avoiding unnecessary memory allocations. |
| Strings containing non-ASCII characters | Verify that the character comparison is based on Unicode code points and not ASCII values, to handle characters from different languages. |
| Very long strings in the input array | Avoid unnecessary string copying to optimize for performance if using an implementation that might lead to out-of-memory issues when copying very long strings frequently. |