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"].
Suppose we chose a set of deletion indices D such that after deletions, the final array has its elements in lexicographic order (A[0] <= A[1] <= A[2] ... <= A[A.length - 1]).
Return the minimum possible value of D.length.
 







Example 1:
Input: ["ca","bb","ac"]
Output: 1
Explanation: 
After deleting the first column, A = ["a", "b", "c"].
Now A is in lexicographic order (ie. A[0] <= A[1] <= A[2]).
We require at least 1 deletion since initially A was not in lexicographic order, so the answer is 1.


Example 2:
Input: ["xc","yb","za"]
Output: 0
Explanation: 
A is already in lexicographic order, so we don't need to delete anything.
Note that the rows of A are not necessarily in lexicographic order:
ie. it is NOT necessarily true that (A[0][0] <= A[0][1] <= ...)


Example 3:
Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: 
We have to delete every column.

 


Note:

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

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        def isSorted(arr, i, j):
            return all(arr[k] <= arr[k+1] for k in range(i, j))
        ans = 0
        ranges = [[0, len(A)-1]]
        for col in zip(*A):
            if not ranges:
                break
            if all(isSorted(col, i, j) for i, j in ranges):
                tmp = []
                for i, j in ranges:
                    start = i
                    for k in range(i, j+1):
                        if col[k] != col[start]:
                            if k - start > 1:
                                tmp.append([start, k-1])
                            start = k   
                    if j + 1 - start > 1:
                        tmp.append([start, j])
                    start = k   
                ranges[:] = tmp
            else:    
                ans += 1
        return ans
            


class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        D = set()
        
        while True:
            changes = False
            last_str = ''
            for i, ch in enumerate(A[0]):
                if i not in D:
                    last_str += ch
            for x in A[1:]:
                this_str = ''
                this_idx = []
                for i, ch in enumerate(x):
                    if i not in D:
                        this_str += ch
                        this_idx.append(i)
                while this_str < last_str:
                    for i in range(len(this_str)):
                        if this_str[i] < last_str[i]:
                            D.add(this_idx[i])
                            this_idx = this_idx[:i] + this_idx[i+1:]
                            this_str = this_str[:i] + this_str[i+1:]
                            last_str = last_str[:i] + last_str[i+1:]
                            changes = True
                            break
                last_str = this_str
            if not changes:
                break
        return len(D)

class Solution:
    def checkLexOrder (self, A: List[str]):
        if A == sorted(A):
            return True
        else:
            return False
    def findDelIndices (self, A: List[str]):
        iter_ = len(A[0])
        to_be_del = []
        temp = ['']*len(A)
        for i in range(iter_):
            if self.checkLexOrder([x[i] for x in A]) == True:
                temp = [temp[j]+A[j][i] for j in range(len(A))]
            else:
                temp_ = [temp[j]+A[j][i] for j in range(len(A))]
                if self.checkLexOrder(temp_) == True:
                    temp = [temp[j]+A[j][i] for j in range(len(A))]
                else:
                    to_be_del.append(i)
        return len(to_be_del)   
    def minDeletionSize(self, A: List[str]) -> int:
        if self.checkLexOrder(A):
            return 0
        else:
            return self.findDelIndices(A)
                
        
        


import copy
class Solution:
    def checkLexOrder (self, A: List[str]):
        if A == sorted(A):
            return True
        else:
            return False
    def findDelIndices (self, A: List[str]):
        iter_ = len(A[0])
        to_be_del = []
        temp = ['']*len(A)
        for i in range(iter_):
            if self.checkLexOrder([x[i] for x in A]) == True:
                temp = [temp[j]+A[j][i] for j in range(len(A))]
            else:
                temp_ = [temp[j]+A[j][i] for j in range(len(A))]
                if self.checkLexOrder(temp_) == True:
                    temp = [temp[j]+A[j][i] for j in range(len(A))]
                else:
                    to_be_del.append(i)
        return len(to_be_del)   
    def minDeletionSize(self, A: List[str]) -> int:
        if self.checkLexOrder(A):
            return 0
        else:
            return self.findDelIndices(A)
                
        
        


class Solution:
    def isArrSorted(self, a) -> tuple((bool, bool)):
        is_exp_sorted = True
        is_eq_sorted = True

        for i, l in enumerate(a):
            if i == len(a) - 1:
                break
            
            if not l < a[i+1]:
                is_exp_sorted = False
            if not l <= a[i+1]:
                is_eq_sorted = False
        return (is_exp_sorted, is_eq_sorted)

    def minDeletionSize(self, A: List[str]) -> int:
        deletion_count = 0
        
        built_A = [''] * len(A)
        
        for i in range(0, len(A[0])):
            letters_at_i = [s[i] for s in A]
            is_exp_sorted, is_eq_sorted = self.isArrSorted(letters_at_i)
            # print(is_exp_sorted, is_eq_sorted)
            
            if is_exp_sorted:
                break
            
            test_A = [built_A[oi] + o[i] for oi, o in enumerate(A)]
            # print(test_A)
            if list(sorted(test_A)) == test_A:
                built_A = test_A
                continue
            else:
                deletion_count += 1
        
        return deletion_count


class Solution:
  def minDeletionSize(self, words: List[str]) -> int:
    n = len( words )
    if n==0:
      return 0
    w = len( words[0] )
    intervals = [[0,n]]
    del_cols = 0
    for col in range(w):
      next_intervals = []
      del_this_col = 0
      for start,end in intervals:
        cprev = words[start][col]
        iprev = start
        for i in range(start+1,end):
          c = words[i][col]
          if c>cprev:
            ## create new interval
            ## reset cprev and iprev
            next_intervals.append( [iprev,i] )
            cprev = c
            iprev = i
          elif c<cprev:
            del_this_col = 1
            del_cols += 1
            break
          pass
        if del_this_col:
          break
        ## add another last interval
        next_intervals.append( [iprev, end] )
        pass
      if not del_this_col:
        intervals = next_intervals
      pass
    return del_cols

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        L = len(A)
        N = len(A[0])
        sort_groups = [[i for i in range(L)]]
        count = 0
        
        for i in range(N):
            
            new_groups = []
            in_order = True
        
            for group in sort_groups:
                new_group = []
                curr_ord = 0
        
                for g_idx in group:
                    
                    char = A[g_idx][i]
                    if ord(char) > curr_ord:
                        if curr_ord != 0:
                            new_groups.append(new_group)
                        new_group = [g_idx]
                        curr_ord = ord(char)
                        
                    elif ord(char) == curr_ord:
                        new_group.append(g_idx)
                        
                        
                    # remove a column
                    else:
                        in_order = False
                        break
                
                if not in_order:
                    break
                
                if new_group != []:
                    new_groups.append(new_group)
                    
            if in_order:
                sort_groups = new_groups
            
            else:
                count += 1
                
        return count

class Solution:
    def minDeletionSize(self, A):
        m, n = len(A), len(A[0])
        first = [False] * m
        res = 0
        for j in range(n):
            for i in range(1, m):
                if not first[i] and A[i][j] < A[i - 1][j]:
                    res += 1
                    break
            else:
                for i in range(1, m):
                    if A[i][j] > A[i - 1][j]:
                        first[i] = True
        return res        

class Solution:
    def minDeletionSize(self, A):
        m, n = len(A), len(A[0])
        first = [-1] * m
        res = 0
        for j in range(n):
            for i in range(1, m):
                if first[i] == -1 and A[i][j] < A[i - 1][j]:
                    res += 1
                    break
            else:
                for i in range(1, m):
                    if A[i][j] > A[i - 1][j] and first[i] == -1:
                        first[i] = j
        return res