Problem

You are given an array of n strings strs, all of the same length.

The strings can be arranged such that there is one on each line, making a grid.

  • For example, strs = ["abc", "bce", "cae"] can be arranged as follows:

abc bce cae

You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.

Return the number of columns that you will delete.

Examples

Example 1:

1
2
3
4
5
6
7

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: The grid looks as follows:
  cba
  daf
  ghi
Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.

Example 2:

1
2
3
4
5
6

Input: strs = ["a","b"]
Output: 0
Explanation: The grid looks as follows:
  a
  b
Column 0 is the only column and is sorted, so you will not delete any columns.

Example 3:

1
2
3
4
5
6
7

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: The grid looks as follows:
  zyx
  wvu
  tsr
All 3 columns are not sorted, so you will delete all 3.

Solution

Method 1 – Column-wise Lexicographical Check

Intuition

The key idea is to check each column of the grid formed by the strings. If any column is not sorted lexicographically from top to bottom, it must be deleted. We count such columns.

Approach

  1. Iterate over each column index.
  2. For each column, compare every character in that column with the character in the previous row.
  3. If any character is less than the character above it, increment the delete counter and break out of the check for that column.
  4. Return the total count of columns to delete.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
  int minDeletionSize(vector<string>& strs) {
    int ans = 0, n = strs.size(), m = strs[0].size();
    for (int col = 0; col < m; ++col) {
      for (int row = 1; row < n; ++row) {
        if (strs[row][col] < strs[row-1][col]) {
          ++ans;
          break;
        }
      }
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func minDeletionSize(strs []string) int {
  ans := 0
  n, m := len(strs), len(strs[0])
  for col := 0; col < m; col++ {
    for row := 1; row < n; row++ {
      if strs[row][col] < strs[row-1][col] {
        ans++
        break
      }
    }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public int minDeletionSize(String[] strs) {
    int ans = 0, n = strs.length, m = strs[0].length();
    for (int col = 0; col < m; col++) {
      for (int row = 1; row < n; row++) {
        if (strs[row].charAt(col) < strs[row-1].charAt(col)) {
          ans++;
          break;
        }
      }
    }
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  fun minDeletionSize(strs: Array<String>): Int {
    var ans = 0
    val n = strs.size
    val m = strs[0].length
    for (col in 0 until m) {
      for (row in 1 until n) {
        if (strs[row][col] < strs[row-1][col]) {
          ans++
          break
        }
      }
    }
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
  def minDeletionSize(self, strs: list[str]) -> int:
    ans = 0
    n, m = len(strs), len(strs[0])
    for col in range(m):
      for row in range(1, n):
        if strs[row][col] < strs[row-1][col]:
          ans += 1
          break
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
  pub fn min_deletion_size(strs: Vec<String>) -> i32 {
    let n = strs.len();
    let m = strs[0].len();
    let mut ans = 0;
    for col in 0..m {
      for row in 1..n {
        if strs[row].as_bytes()[col] < strs[row-1].as_bytes()[col] {
          ans += 1;
          break;
        }
      }
    }
    ans
  }
}

Complexity

  • Time: O(n * m) where n is the number of strings and m is the length of each string.
  • Space: O(1) (ignoring input storage).