Delete Columns to Make Sorted

Problem Description

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:

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:

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:

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.

Constraints

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

Solution

Python

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        count = 0
        for col in range(len(strs[0])):
            for row in range(1, len(strs)):
                if strs[row][col] < strs[row - 1][col]:
                    count += 1
                    break
        return count

# Example usage:
solution = Solution()
print(solution.minDeletionSize(["cba","daf","ghi"]))  # Output: 1

C++

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int count = 0;
        for (int col = 0; col < strs[0].size(); ++col) {
            for (int row = 1; row < strs.size(); ++row) {
                if (strs[row][col] < strs[row - 1][col]) {
                    count += 1;
                    break;
                }
            }
        }
        return count;
    }
};

// Example usage:
int main() {
    Solution solution;
    vector<string> strs = {"cba","daf","ghi"};
    cout << solution.minDeletionSize(strs) << endl;  // Output: 1
    return 0;
}

Java

class Solution {
    public int minDeletionSize(String[] strs) {
        int count = 0;
        for (int col = 0; col < strs[0].length(); ++col) {
            for (int row = 1; row < strs.length; ++row) {
                if (strs[row].charAt(col) < strs[row - 1].charAt(col)) {
                    count += 1;
                    break;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] strs = {"cba", "daf", "ghi"};
        System.out.println(solution.minDeletionSize(strs));  // Output: 1
    }
}

JavaScript

var minDeletionSize = function (strs) {
  let count = 0;
  for (let col = 0; col < strs[0].length; ++col) {
    for (let row = 1; row < strs.length; ++row) {
      if (strs[row][col] < strs[row - 1][col]) {
        count += 1;
        break;
      }
    }
  }
  return count;
};

// Example usage:
console.log(minDeletionSize(["cba", "daf", "ghi"])); // Output: 1