Delete Columns To Make Sorted Iii - Leetcode Solution

Problem:

Given a string array words, find the minimum number of columns that can be deleted to make all words sorted in non-decreasing order.

A column is a set of characters that can be read from top to bottom in the matrix.

It is guaranteed that only lowercase English letters will be used in the strings.

Example 1:

Input: ["babca","bbazb"] Output: 3 Explanation: Columns a, b, and c have to be deleted.

Example 2:

Input: ["edcba"] Output: 4 Explanation: All columns have to be deleted.

Example 3:

Input: ["ghi","def","abc"] Output: 0 Explanation: The columns don't need to be deleted as the words are already sorted in non-decreasing order.

Solution:

To solve this problem, you need to keep track of the sorted order of the words.

Create a variable sorted_order, initialized to true.

Loop through the first word in the array of words and compare it to the next word in the array of words.

If the letters in the row are not sorted in non-decreasing order, the sorted_order should be set to false.

If the letters in the row are sorted in non-decreasing order, you should continue by comparing the next row.

If two rows have the same letter in the given column, then we need to compare the next column until we find that one word is greater than the other.

If the sorted_order is true for all rows, then you can return 0 because no columns need to be deleted.

If the sorted_order is false for a column, then you need to count the number of columns you need to delete so that all words can be sorted.

The final result is the number of columns you need to delete.

Here is the Python implementation:

class Solution: def minDeletionSize(self, words: List[str]) -> int: n = len(words[0]) count = 0 for c in range(n): for i in range(1, len(words)): if words[i-1][c] > words[i][c]: count += 1 break return count

1