Problem Description

We are given an array A of N lowercase letter strings, all of the same length. We are allowed to pick any set of indices and for each string, we delete all the characters in those chosen indices.

For instance, suppose we have an array A = ["abcdef","uvwxyz"] and we choose deletion indices {0, 2, 3}, then the array post deletions would be ["bef","vyz"].

Now, we need to choose a set of deletion indices D such that after we perform the deletions, the final array's elements are in lexicographic order (meaning, if you compare the elements of array A, they follow the same order as the order of letters in a dictionary, for example A[0] <= A[1] <= A[2] ... <= A[A.length - 1]).

Our task is to return the minimum possible length of D.

Approach

The solution uses the greedy algorithm approach, where it incrementally makes choices that seem optimal at the calling time, hoping to reach the global optimum solution.

Here, we track whether each pair of adjacent strings is already sorted or not. This is done using a boolean array sorted[]. This array helps us remember which pairs of adjacent strings are sorted so that we don't repeat the comparisons.

Then, we iterate over all positions (columns) and check every pair of adjacent strings (A[i] and A[i + 1]).

If the pair is out of order, it means that we must delete this column, break the loop, and go to the next position (column). But if the pair is in order, we update the sorted[] array and track this information for the next position.

Java Solution

This java solution implements the above approach, iterates over the columns, checks every pair of adjacent strings, and deletes the column if needed. It uses an array to keep track of already sorted pairs.

1
2java
3class Solution {
4  public int minDeletionSize(String[] A) {
5      int n = A[0].length();
6      int ans = 0;
7      boolean[] sorted = new boolean[A.length - 1];
8      for (int j = 0; j < n; ++j) {
9          int i;
10          for(i = 0; i + 1 < A.length; ++i)
11              if (!sorted[i] && A[i].charAt(j) > A[i + 1].charAt(j)) {
12                  ans++;
13                  break;
14              }
15          if (i + 1 == A.length)
16              for(i = 0; i + 1 < A.length; ++i)
17                  sorted[i] = sorted[i] || A[i].charAt(j) < A[i + 1].charAt(j);
18      }
19      return ans;
20  }
21}

This approach ensures that we only delete the minimum number of columns needed to make the elements of the array lexicographically ordered. This is achieved by only deleting a column when no other option is available to get the required ordering, and keeping track of already sorted pairs helps in optimizing the process.# Python Solution

The Python solution works similar to the Java example. First, we mark which pairs are already in lexicographical order, then we iterate through the characters in the strings one by one, and mark them as sorted. If we find a pair that is out of order, we increment our answer and break our current cycle to iterate to the next character.

1
2python
3def minDeletionSize(A):
4    n, ans = len(A[0]), 0
5    sorted = [False] * (len(A) - 1)
6    
7    for j in range(n):
8        temp_sorted = sorted[:]
9        for i in range(len(A) - 1):
10            if A[i][j] > A[i + 1][j] and not sorted[i]:
11                ans += 1
12                temp_sorted = sorted
13                break
14            elif A[i][j] < A[i + 1][j] and not sorted[i]:
15                temp_sorted[i] = True
16        sorted = temp_sorted
17                
18    return ans

JavaScript Solution

The JavaScript solution follows the same logic. It creates an array to mark which pairs are already sorted. Then, it iterates through each string's characters in the array. If it finds a pair out of order, it increments the result and breaks the loop. If it finds a pair in order, it marks it as sorted.

1
2javascript
3function minDeletionSize(A) {
4    let ans = 0;
5    let sorted = new Array(A.length - 1).fill(false);
6    search: for (let j = 0; j < A[0].length; ++j) {
7        for (let i = 0; i < A.length - 1; ++i) {
8            if (!sorted[i] && A[i].charAt(j) > A[i + 1].charAt(j)) {
9                ans++;
10                continue search;
11            }
12        }
13        for (let i = 0; i < A.length - 1; ++i)
14            if (A[i].charAt(j) < A[i + 1].charAt(j))
15                sorted[i] = true;
16    }
17    return ans;
18}

In all three solutions, the time complexity is O(n*a), where n is the length of the strings and a is the length of the array. The space complexity is O(a), to store the sorted array. Using this approach, we can efficiently find the minimum number of deletions to make the array lexicographically ordered.