Problem

You are given an array of n strings strs, 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 strs = ["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 answer such that after deletions, the final array has its elements in lexicographic order (i.e., strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Return the minimum possible value of answer.length.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3

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

Constraints

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Solution

Method 1 – Greedy Pairwise Comparison

Intuition

The key idea is to process columns from left to right, greedily deleting columns that break the lexicographical order between any two adjacent strings. We only keep columns that do not cause any disorder, and once a pair of strings is confirmed to be ordered, we never need to check them again.

Approach

  1. Initialize a variable ans to count the number of columns to delete.
  2. Use a boolean array to track which adjacent pairs are already confirmed to be in order.
  3. For each column from left to right:
  • For each pair of adjacent strings not yet confirmed to be in order:
    • If the current column causes a disorder (i.e., strs[i][col] > strs[i+1][col]), increment ans and skip to the next column.
  • Otherwise, update the boolean array for pairs that are now confirmed to be in order (strs[i][col] < strs[i+1][col]).
  1. Return ans as the minimum number of columns to delete.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
   int minDeletionSize(vector<string>& strs) {
      int n = strs.size(), m = strs[0].size(), ans = 0;
      vector<bool> sorted(n - 1, false);
      for (int col = 0; col < m; ++col) {
        bool needDel = false;
        for (int i = 0; i < n - 1; ++i) {
           if (!sorted[i] && strs[i][col] > strs[i + 1][col]) {
              needDel = true;
              break;
           }
        }
        if (needDel) {
           ++ans;
           continue;
        }
        for (int i = 0; i < n - 1; ++i) {
           if (strs[i][col] < strs[i + 1][col])
              sorted[i] = true;
        }
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func minDeletionSize(strs []string) int {
   n, m := len(strs), len(strs[0])
   ans := 0
   sorted := make([]bool, n-1)
   for col := 0; col < m; col++ {
      needDel := false
      for i := 0; i < n-1; i++ {
        if !sorted[i] && strs[i][col] > strs[i+1][col] {
           needDel = true
           break
        }
      }
      if needDel {
        ans++
        continue
      }
      for i := 0; i < n-1; i++ {
        if strs[i][col] < strs[i+1][col] {
           sorted[i] = true
        }
      }
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
   public int minDeletionSize(String[] strs) {
      int n = strs.length, m = strs[0].length(), ans = 0;
      boolean[] sorted = new boolean[n - 1];
      for (int col = 0; col < m; col++) {
        boolean needDel = false;
        for (int i = 0; i < n - 1; i++) {
           if (!sorted[i] && strs[i].charAt(col) > strs[i + 1].charAt(col)) {
              needDel = true;
              break;
           }
        }
        if (needDel) {
           ans++;
           continue;
        }
        for (int i = 0; i < n - 1; i++) {
           if (strs[i].charAt(col) < strs[i + 1].charAt(col)) {
              sorted[i] = true;
           }
        }
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
   fun minDeletionSize(strs: Array<String>): Int {
      val n = strs.size
      val m = strs[0].length
      var ans = 0
      val sorted = BooleanArray(n - 1)
      for (col in 0 until m) {
        var needDel = false
        for (i in 0 until n - 1) {
           if (!sorted[i] && strs[i][col] > strs[i + 1][col]) {
              needDel = true
              break
           }
        }
        if (needDel) {
           ans++
           continue
        }
        for (i in 0 until n - 1) {
           if (strs[i][col] < strs[i + 1][col]) {
              sorted[i] = true
           }
        }
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
   def minDeletionSize(self, strs: list[str]) -> int:
      n, m = len(strs), len(strs[0])
      ans = 0
      sorted_pairs = [False] * (n - 1)
      for col in range(m):
        need_del = False
        for i in range(n - 1):
           if not sorted_pairs[i] and strs[i][col] > strs[i + 1][col]:
              need_del = True
              break
        if need_del:
           ans += 1
           continue
        for i in range(n - 1):
           if strs[i][col] < strs[i + 1][col]:
              sorted_pairs[i] = True
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
   pub fn min_deletion_size(strs: Vec<String>) -> i32 {
      let n = strs.len();
      let m = strs[0].len();
      let mut ans = 0;
      let mut sorted = vec![false; n - 1];
      let strs: Vec<Vec<u8>> = strs.into_iter().map(|s| s.into_bytes()).collect();
      for col in 0..m {
        let mut need_del = false;
        for i in 0..n - 1 {
           if !sorted[i] && strs[i][col] > strs[i + 1][col] {
              need_del = true;
              break;
           }
        }
        if need_del {
           ans += 1;
           continue;
        }
        for i in 0..n - 1 {
           if strs[i][col] < strs[i + 1][col] {
              sorted[i] = true;
           }
        }
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n * m) where n is the number of strings and m is the length of each string.
  • 🧺 Space complexity: O(n) for the auxiliary array tracking sorted pairs.