Problem Description
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. 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.
Key Insights
- The problem requires determining which columns (indices) can be deleted to ensure that the remaining strings are sorted in lexicographic order.
- A greedy approach can be used, where we check each column one by one and decide whether to delete it based on the current order of strings.
- We need to keep track of the "last sorted" index to ensure that any newly considered strings are in order with respect to previously sorted strings.
Space and Time Complexity
Time Complexity: O(n * m), where n is the number of strings and m is the length of each string.
Space Complexity: O(1), since we are using a constant amount of extra space.
Solution
The approach involves iterating through the columns of the strings and checking if the strings are in sorted order when considering the current column. If a column causes the strings to be out of order, we mark that column for deletion. The algorithm maintains the sorted order by comparing adjacent strings, and if they are not in order, it checks if the current column can be deleted to restore order. The final count of deleted columns is returned.