Python3 | Time: 4 ms (44.12%) | Memory: 16.7 MB (38.84%)
Intuition\nTo ensure the rows are lexicographically sorted, we need to evaluate each column to see if removing it would help achieve the required order. Our goa
# Intuition\nTo ensure the rows are lexicographically sorted, we need to evaluate each column to see if removing it would help achieve the required order. Our goal is to identify and count the minimum number of columns to delete so that the rows remain sorted when read left to right. By keeping track of which rows are already sorted up to each column, we can focus on identifying only the columns that disrupt this order.\n\n# Approach\n1. **Track Row Sorting State:** Use a list `current` to track pairs of rows that are already sorted up to the `current` column. This allows us to avoid unnecessary deletions in columns that don\u2019t impact the overall order.\n\n2. **Iterate Through Columns:** For each column, check if it maintains the order based on the previous column states in current. If any row pair violates the sorted order at the current column, mark this column for deletion and stop checking further for this column.\n\n3. **Update Sorted State When Keeping Columns:** If a column can be kept, update the `current` state to reflect any new row pairs that are confirmed to be sorted based on this column.\n\n4. **Return the Count of Deletions:** At the end of the loop, the count of columns marked for deletion will represent the minimum number of deletions required to keep the rows sorted.\n\n# Complexity\n- Time complexity:\n$$\\mathcal{O}(m \\cdot n)$$, where $$n$$ is the number of strings and $$m$$ is the length of each string. We iterate through each column and potentially each row within that column.\n\n- Space complexity:\n$$\\mathcal{O}(n)$$, where $$n$$ is the number of strings, due to the current list that tracks the sorted state of row pairs.\n\n# Code\n```python3 []\nclass Solution:\n    def minDeletionSize(self, strs: List[str]) -> int:\n        count = 0\n        current = [False] * (len(strs) - 1)  # Track rows that need checking\n\n        for pos in range(len(strs[0])):\n            keep = True\n            for i in range(1, len(strs)):\n                # Check if the previous column was already sorted for this pair\n                if not current[i - 1] and strs[i][pos] < strs[i - 1][pos]:\n                    count += 1\n                    keep = False\n                    break\n            \n            # If we kept this column, update the \'current\' state to reflect ties\n            if keep:\n                for i in range(1, len(strs)):\n                    if strs[i][pos] > strs[i - 1][pos]:\n                        current[i - 1] = True\n\n        return count\n            \n                \n\n\n            \n\n        \n```
['Python3']