Problem:

You are given an array of n strings strs, all of the same length.

The strings can be arranged such that there is one on each line, making a grid. For example, strs = ["abc", "bce", "cae"] can be arranged as:

abc
bce
cae

You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted while column 1 ('b', 'c', 'a') is not, so you would delete column 1.

Return the number of columns that you will delete.

Example 1:

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: The grid looks as follows:
  cba
  daf
  ghi
Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.

Example 2:

Input: strs = ["a","b"]
Output: 0
Explanation: The grid looks as follows:
  a
  b
Column 0 is the only column and is sorted, so you will not delete any columns.

Example 3:

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: The grid looks as follows:
  zyx
  wvu
  tsr
All 3 columns are not sorted, so you will delete all 3.

Constraints:

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 1000
• strs[i] consists of lowercase English letters.

Solution:

Intuition

Iterate over each character of the strings, check if the current character ascii value is more than previous string's this index's character's ascii value

Approach

In outer loop, iterate over the length of the string. In inner loop iterate over the strings of the list. For each index postion, check if current string's current characters's (character in index position) ascii value is less than previous one. If found, increment count variable and break the inner loop, else keep checking for next string. Reset last_char variable after checking all the strings for current index

Complexity

• Time complexity: O(n∗len(n))

• Space complexity: O(1)

Code

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        count = 0
        for i in range(len(strs[0])):
            last_char = 0
            for str in strs:
                if ord(str[i]) < last_char:
                    count += 1
                    break
                else:
                    last_char = ord(str[i])
        return count