We are given an array A of N lowercase letter strings, all of the same length.
Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have an array A = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"], and the remaining columns of A are ["b","v"], ["e","y"], and ["f","z"].  (Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]]).
Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.
Return the minimum possible value of D.length.
 
Example 1:
Input: A = ["cba","daf","ghi"]
Output: 1
Explanation: 
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.

Example 2:
Input: A = ["a","b"]
Output: 0
Explanation: D = {}

Example 3:
Input: A = ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}

 
Constraints:

1 <= A.length <= 100
1 <= A[i].length <= 1000

Difficulty: introductory

Starter code:

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        

Solutions:
class Solution:
    def minDeletionSize(self, A: List[str]) -> int:        
        return sum([list(col) != sorted(col) for col in zip(*A)])
            


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:        
        return sum(list(col) != sorted(col) for col in zip(*A))
            


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        if (len(A) <= 1):
            return 0
        elif len(A[1]) == 1:
            return 0
        D = []
        for i in range(0, len(A[0])):
            col = [a[i] for a in A]
            col_sort = sorted(col)
            if col != col_sort:
                D.append(i)
        return len(D)


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        n = len(A[0])
        res = 0
        for i in range(n):
            col = [a[i] for a in A]
            if col != sorted(col):
                res += 1
        return res

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        result=0
        M=len(A[0])
        for i in range(M):
            col=[row[i] for row in A]
            if col!=sorted(col):
                result+=1
        return result
            
        


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        ans = 0
        for i,word in enumerate(zip(*A)):
            for j in range(len(word)-1):
                if word[j] > word[j+1]:
                    ans += 1
                    break
        
        return ans

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
      delete_size = 0
      cols = zip(*A)
      for col in cols:
        for a, b in zip(col, col[1:]):
          if a > b:
            delete_size += 1
            break
      return delete_size

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        D = 0
        for col in zip(*A):
            p = chr(0)
            for c in col:
                if c < p:
                    D += 1
                    break
                p = c
        return D

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        return sum(any(i > j for i, j in zip(t, t[1:])) for t in zip(*A))

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        count = 0
        length = len(A[0])
        noofstr = len(A)
        #print(length, noofstr)
        
        for i in range(length):
            increasing = True
            for j in range(1,noofstr):
                if A[j][i] < A[j-1][i]:
                    increasing = False
                    break
            if increasing:
                count += 1
        return (length - count)

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


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        return sum([list(i) != sorted(i) for i in zip(*A)])

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        res = []
        rows = len(A)
        cols = len(A[0])
        for c in range (cols):
            for r in range (rows-1):
                if A[r][c] > A[r+1][c]:
                    res.append(-1)
                    break
               
        return res.count(-1)

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

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        return sum(not all(c <= d for c, d in zip(col, col[1:])) for col in zip(*A))


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        count = 0
        length = len(A[0])
        noofstr = len(A)
        print(length, noofstr)
        
        for i in range(length):
            increasing = True
            for j in range(1,noofstr):
                if A[j][i] < A[j-1][i]:
                    increasing = False
                    break
            if increasing:
                count += 1
        return (length - count)

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        n = len(A[0])
        del_indices = []
        for j in range(n):
            for i in range(len(A) - 1):
                if A[i][j] > A[i + 1][j]:
                    del_indices.append(j)
                    break
            continue
        return len(del_indices)
            
            


class Solution(object):
    def minDeletionSize(self, A):
        ans = 0
        for col in zip(*A):
            if any(col[i] > col[i+1] for i in range(len(col) - 1)):
                ans += 1
        return ans

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        ans=0
        for col in zip(*A):
            if any(col[i]>col[i+1] for i in range(len(col)-1)):
                ans+=1
        return ans

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        res = 0
        for i in range(len(A[0])):
            for j in range(1,len(A)):
                if A[j][i] < A[j-1][i]:
                    res+=1
                    break
                    
                    
        return res

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        c_l = len(A[0])
        A_l = len(A)
        count = 0
        for i in range(c_l):
            string = [col[i] for col in A]
            # print(string)
            for j in range(1, A_l):
                if string[j] < string[j-1]:
                    count += 1
                    break
        return count

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        count = 0
        for col in zip(*A):
            if list(col) != sorted(col):
                count += 1
        return count
            
            


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

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        rows = len(A)
        cols = len(A[0])
        out = []
        for i in range(cols):
            temp = []
            for j in range(rows):
                temp.append(A[j][i])
            out.append(temp)
        count = 0
        for i in out:
            if i != sorted(i):
                count+=1
        return count

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        columns = [''] * len(A[0]) 
        for string in A:
            for i, char in enumerate(string):
                columns[i]+=char
        count = 0
        for word in columns:
            if word != ''.join(sorted(word)):
                count += 1
        return count
            


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        l = list(A[0])
        
        for i in A:
            for j in range(len(i)):
                if l[j] == 'A':
                    continue
                if i[j] < l[j]:
                    l[j] = 'A'
                else:
                    l[j] = i[j]
                # print(l)
        # print(l)
        return l.count('A')

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        indiciesToRemove = []
        columns = len(A[0])
        rows = len(A)
        for col in range(0, columns):
            previous = chr(0)
            for row in range(0, rows):
                if A[row][col] < previous:
                    indiciesToRemove.append(col)
                    break
                previous = A[row][col]
                
                
        return len(indiciesToRemove)
                


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        return sum([x[i] for x in A] != sorted([x[i] for x in A]) for i in range(len(A[0])))        

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        set_dim = 0
        for column in range(len(A[0])):
            for row in range(len(A) - 1):
                if A[row][column] > A[row + 1][column]:
                    set_dim += 1
                    break
        
        return set_dim


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

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        # check ascending order = comparison O(1)
        
        do_not_remove_idx = []
        for idx in range(len(A[0])):
            tmp = [a[idx] for a in A]
                    
            if any(x > y for x, y in zip(tmp, tmp[1:])):
                do_not_remove_idx.append(idx)
        
        return len(do_not_remove_idx)

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

class Solution:
    def minDeletionSize(self, A):
        return sum(list(col) != sorted(col) for col in zip(*A))

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        t = 0
        i = 0
        while i < len(A[0]):
            j = 0
            last = chr(0)
            while j < len(A):
                if A[j][i] >= last:
                    last = A[j][i]
                else:
                    t += 1
                    break
                j += 1
            i += 1
        return t

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
    
        count = 0

        for i in range(len(A[0])):
            if not self.isSorted(list([x[i] for x in A])):
                count+=1

        return count
    
    
    
    def isSorted(self,list_char):
        for i in range(1,len(list_char)):
            if list_char[i-1]>list_char[i]:
                return False
            
        return True


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        result = 0
        for i in range(len(A[0])):
            last = A[0][i]
            for j in range(1, len(A)):
                if ord(last) > ord(A[j][i]):
                    result += 1
                    break
                last = A[j][i]
        
        return result
        


class Solution:
    def minDeletionSize(self, A):
        word_len = len(A[0])
        count = 0

        for j in range(word_len):
            for i in range(1, len(A)):
                if A[i][j] < A[i-1][j]:
                    count+=1
                    break
        return count

# brute force
class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        res = 0
        for j in range(len(A[0])):
            for i in range(len(A) - 1):
                if ord(A[i][j]) > ord(A[i + 1][j]):
                    res += 1
                    break
        return res

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        if len(A) == 0:
            return 0
        n = len(A[0])
        cnt = 0
        for i in range(n):
            is_sorted = True
            for j in range(len(A) - 1):
                if A[j][i] > A[j + 1][i]:
                    is_sorted = False
                    break
            if not is_sorted:
                cnt += 1
        return cnt

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        if not A:
            return 0
        count=0
        prev=''
        for i in range(0,len(A[0])):
            for j in range(1,len(A)):
                if ord(A[j-1][i])>ord(A[j][i]):
                    count+=1
                    break
        return count
                    


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        ans = 0
        for col in zip(*A):
            if any(col[i] > col[i+1] for i in range(len(col) - 1)):
                ans += 1
        return ans

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        count=0
        for i in zip(*A):
            if ''.join(i)!=''.join(sorted(list(map(''.join,i)))):
                count+=1
        return count

class Solution:
    # check all non-decreasing order exists and find all peaks
    def findAllPeaks(self, A:List[str]) -> set():
        if (len(A[0]) <= 1):
            return set()
        
        column_number = len(A[0])
        row_number = len(A)
        
        pre_letter_to_int = [-1 for i in range(column_number)]
        result = set()
        for c in range(column_number):
            for r in range(row_number):
                if ord(A[r][c]) < pre_letter_to_int[c]:
                    # find a peak, pre_letter_to_int
                    result.add(c)
                    break
                else:
                    pre_letter_to_int[c] = ord(A[r][c])
        return result
                    
                    
            
    
    def minDeletionSize(self, A: List[str]) -> int:
        return len(self.findAllPeaks(A))


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        size = len(A[0])
        setd = set([i for i in range(size)])
        for i in range(len(A) - 1) :
            if not setd :
                return size
            setn = set()
            for digit in setd:
                if A[i][digit] > A[i+1][digit] :
                    setn.add(digit)
            setd -= setn
         
        return size - len(setd)

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        N = len(A[0])
        # print(A[0])
        count = 0
        for i in range(N):
            temp = []
            for j in range(len(A)):
                temp.append(A[j][i])
            
            # print(temp)
            # print(sorted(temp))
            if temp != sorted(temp):
                count += 1
                
        return count

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        return sum(any(A[j][i] < A[j - 1][i] for j in range(1, len(A))) for i in range(len(A[0])))

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        for i in range(len(A)):
            self.convertCharsToIntArray(i,A)
        counts = 0
        for i in range(len(A[0])):
            checker = False
            for j in range(1,len(A)):
                if A[j-1][i] > A[j][i]:
                    checker = True
            if checker:
                counts += 1
        return counts 
        
    def convertCharsToIntArray(self,i,A):
        chars = A[i]
        array = []
        for char in chars:
            array.append(ord(char))
        A[i] = array


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        count = 0
        col = 0
        while col < len(A[0]):
            row = 0
            while row < len(A)-1:
                if ord(A[row][col] ) > ord(A[row+1][col]):
                    count += 1
                    break
                row += 1
            col += 1
        return count


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        for i in range(len(A)):
            self.convertCharsToIntArray(i,A)
            
        counts = 0
        for i in range(len(A[0])):
            checker = False
            for j in range(1,len(A)):
                if A[j-1][i] > A[j][i]:
                    checker = True
            if checker:
                counts += 1
        return counts 
        
    def convertCharsToIntArray(self,i,A):
        chars = A[i]
        array = []
        for char in chars:
            array.append(ord(char))
        A[i] = array


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        ans = []
        j = 0
        for i in range(len(A[0])):
            temp = []
            for k in range(len(A)):
                temp.append(A[k][j])
            ans.append(temp)
            j += 1
        count = 0
        for i in ans:
            temp = i[:]
            temp.sort()
            if temp != i:
                count += 1
        return count

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        count = 0
        for i in range(0, len(A[0])):
            maximum = A[0][i]
            inDecreasingOrder = True
            j = 1
            while j < len(A):
                val = A[j][i]
                if val < maximum:
                    inDecreasingOrder = False
                    break
                maximum = val
                j   += 1
            if inDecreasingOrder:
                count += 1
        return len(A[0])-count


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        ans = 0
        for col in zip(*A):
            if any(col[i] > col[i+1] for i in range(len(col) - 1)): # Delete decreasing ones
                ans += 1
        return ans


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        
        ans = 0
        for i in zip(*A):
            if list(i) != sorted(i):
                ans += 1
        return ans


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        prev = A[0]
        indices = {i for i in range(len(prev))}
        remove = set()
        for a in A[1:]:
            remove.clear()
            for i in indices:
                if prev[i] > a[i]:
                    remove.add(i)
            indices -= remove
            prev = a
            # if len(indices) == 0: break
        return len(prev) - len(indices)