Delete Columns to Make Sorted II

Problem Id: 955 Difficulty: Medium


Intuition

Solution


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        cur = [""] * len(A)
        ans = 0

        for col in zip(*A):
            cur2 = [s1 + s2 for s1, s2 in zip(cur, col)]
            if self.is_sorted(cur2):
                cur = cur2
            else:
                ans += 1
        return ans

    @staticmethod
    def is_sorted(A):
        return all(A[i] <= A[i + 1] for i in range(len(A) - 1))