Delete Columns to Make Sorted

The goal is to count the number of columns that are not sorted in lexicographic order.

Here’s a step by step approach for this problem:

  1. Start by setting a counter to 0. This counter will keep track of the number of columns that are not sorted.

  2. Assume that the length of each string in the list is m. Create a nested loop where the outer loop runs from 0 to m-1 (to iterate over columns), and the inner loop runs from 1 to n-1 (to iterate over rows).

  3. In the inner loop, compare the character at the current column in the current row with the character at the same column in the previous row. If the character in the current row is smaller, it means that the column is not sorted. In this case, increment the counter by 1 and break the inner loop to move to the next column.

  4. Once all columns have been checked, return the counter.

Python solution:

1
2
3
4
5
6
7
8
9

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

This solution works by iterating over the characters in each column and checking if they are in sorted order. If they are not, it increments the counter. After all columns have been checked, it returns the counter.