g0901_1000.s0955_delete_columns_to_make_sorted_ii.Solution

public class Solution extends Object

955 - Delete Columns to Make Sorted II.Medium You are given an array of <code>n</code> strings <code>strs</code>, 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 <code>strs = ["abcdef","uvwxyz"]</code> and deletion indices <code>{0, 2, 3}</code>, then the final array after deletions is <code>["bef", "vyz"]</code>. Suppose we chose a set of deletion indices <code>answer</code> such that after deletions, the final array has its elements in lexicographic order (i.e., <code>strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]</code>). Return the minimum possible value of <code>answer.length</code>. 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: <ul> <li><code>n == strs.length</code></li> <li><code>1 <= n <= 100</code></li> <li><code>1 <= strs[i].length <= 100</code></li> <li><code>strs[i]</code> consists of lowercase English letters.</li> </ul>

Constructor Summary

Constructors

Constructor

Description

Solution()
Method Summary

Modifier and Type

Method

Description

int

minDeletionSize(String[] strs)

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- Solution
  
  public Solution()
Method Details
- minDeletionSize
  
  public int minDeletionSize(String[] strs)

Class Solution

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Details

Solution

Method Details

minDeletionSize