Leetcode 992 Solution

This article provides solution to leetcode question 992 (delete-columns-to-make-sorted-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 992" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/delete-columns-to-make-sorted-ii

Solution

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        n = len(A[0])
        cuts = [False] * len(A)
        ans = 0
        for i in range(n):
            cur = chr(ord('a') - 1)
            next_cuts = list(cuts)
            for j, word in enumerate(A):
                if not next_cuts[j]:
                    if word[i] < cur:
                        ans += 1
                        break
                    elif word[i] > cur:
                        next_cuts[j] = True

                cur = word[i]
            else:
                cuts = next_cuts

        return ans