#960
Delete Columns to Make Sorted III
specialist · 955 · lc hard +32 · verified · 72.7% accepted · 868 likes · top 82%
Description
Given n equal-length strings strs as a grid, delete the fewest columns so that within every individual remaining row, characters appear in non-decreasing order left to right. Return the minimum number of columns to delete.
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.
Code
1
2
3