Delete Columns to Make Sorted II
You are given an array of n strings strs, all of the same length.
You may choose any deletion indices, and you delete all the characters in those indices for each string.
For example, if strs = ["abcdef", "uvwxyz"] and the deletion indices are {0, 2, 3}, then the final array after deletions is ["bef", "vyz"].
Suppose you chose a set of deletion indices answer such that after deletions, the final array has its elements in lexicographic order, meaning 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
1After deleting the first column, strs becomes ["a", "b", "c"], which is lexicographically sorted, and at least one deletion is required because the original array was not sorted.
Example 2
Input
strs = ["xc","yb","za"]Output
0The array is already in lexicographic order, so no deletions are needed.
Constraints
- n == strs.length
- 1 <= n <= 100
- 1 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.