Delete Columns to Make Sorted II

LeetCode Q 955 - Delete Columns to Make Sorted II

We are given an array A of N lowercase letter strings, all of the same length. Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”,”vyz”].

Suppose we chose a set of deletion indices D such that after deletions, the final array has its elements in lexicographic order (A[0] <= A[1] <= A[2] … <= A[A.length - 1]).

Return the minimum possible value of D.length.

Example 1: Input: ["ca","bb","ac"] ; Output: 1
Explanation:
After deleting the first column, A = [“a”, “b”, “c”].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.

Example 2: Input: ["xc","yb","za"] ; Output: 0
Explanation:
A is already in lexicographic order, so we don’t need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= …)

Example 3: Input: ["zyx","wvu","tsr"] ; Output: 3
Explanation:
We have to delete every column.

Note:

• 1 <= A.length <= 100
• 1 <= A[i].length <= 100

Similar Question: Delete Columns to Make Sorted

Solution

We need an additional boolean array isValid. isValid[i] = true denotes if the ith string is lexicographically smaller than the i + 1th string. The key point is we delete a column if and only if !isSorted[i] && strs[i].charAt(j) > strs[i + 1].charAt(j).

Let’s explain the algorithm in detail with the following example.

Input: ["xgag","xfba","yfac"]

• First Round: compare the first column, we find x = x < y which is valid, so res = 0. Update isSorted[1] = true, since x < y.
• Second Round: compare the second column, i.e. g > f = f, so we should delete the second column, then res = 1;
• Third Round: compare the third column, i.e. a < b > a. In this case we don’t need to delete the third column, since isSorted[1] = true. Say we have already found that "xba" < "yac", there is no need to let them become "xa" and "yc". Then res keeps the same, i.e. res = 1. Update isValid[0] = true, since a < b.
• Fourth Round: compare the fourth column, i.e. g > a < c. Since isSorted[0] = true, don’t delete the fourth column. Therefore, the final result is 1.

Code:

public int minDeletionSize(String[] A) {

	if (A.length == 1) return 0;

	int res = 0, lenArr = A.length, lenStr = A[0].length();

	boolean[] isSorted = new boolean[A.length - 1];

	for (int i = 0; i < lenStr; i++) {

		int j = 0;
	
		for (; j + 1 < lenArr; j++) {

			if (!isSorted[j] && A[j].charAt(i) > A[j + 1].charAt(i)) {
				res++; break;
			}
		}

		if (j != lenArr - 1) continue;

		for(j = 0; j < lenArr; j++) {
			if (A[j].charAt(i) < A[j + 1].charAt(i))
				isSorted[j] = true;
		}
	}

	return res;
}