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

We may choose any deletion indices, and we delete all the characters in those indices for each string.

For example, if we have strs = ["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 answer such that after deletions, the final array has its elements in lexicographic order (i.e., strs[0] &lt;= strs[1] &lt;= strs[2] &lt;= ... &lt;= strs[n - 1]). Return the minimum possible value of answer.length.

&nbsp;
Example 1:

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


Example 2:

Input: strs = ["xc","yb","za"]
Output: 0
Explanation: 
strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] &lt;= strs[0][1] &lt;= ...)


Example 3:

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


&nbsp;
Constraints:


	n == strs.length
	1 &lt;= n &lt;= 100
	1 &lt;= strs[i].length &lt;= 100
	strs[i] consists of lowercase English letters.


class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)
        col_size = len(strs[0])
        # a b c d e f g h i j k l m n o p q r s t u v w x y z
        
        i = 0
        ans = 0
        
        def getRemoved(idx):
             # removing the idx column 
            for x in range(n):           
                strs[x] = strs[x][:idx] + strs[x][idx+1:]
        
        while i < col_size:
            tmp = strs[0][:i+1]
            flag = True
            similar = False
            
            for j in range(1,n):                 
                if  strs[j][:i+1] < tmp :
                    # previous element is larger ( unsorted )
                    flag = False
                    break
                
                elif strs[j][:i+1] > tmp : 
                    # previous element is smaller ( sorted )
                    tmp = strs[j][:i+1]
                
                else:
                    # previous element is equal ( not clear )
                    tmp = strs[j][:i+1]
                    similar = True
            
            if flag == True and similar == False:
                # all are sorted and we are ready to return ans
                return ans
            
            elif flag == True and similar == True:
                # all are sorted but can't be decided for further columns. check for next col
                i += 1
            
            elif flag == False:
                # unsorted column = removal
                getRemoved(i)
                # increment the answer and since we removed i th col decrement col_size
                ans += 1
                col_size -= 1
        
        return ans
class Solution {
    public int minDeletionSize(String[] strs) {
       boolean[] sorted = new boolean[strs.length];
        int res = 0;
        for(int i = 0;i<strs[0].length();i++){
            int j = 0;
           for(;j<strs.length-1;j++){
              if(!sorted[j]&&strs[j].charAt(i)>strs[j+1].charAt(i)){
                  res++;
                  break;
              }  
            }
            if(j<strs.length-1){
                continue;
            }
            j = 0;
            for(;j<strs.length-1;j++){
                if(strs[j].charAt(i)<strs[j+1].charAt(i)){
                    sorted[j] = true;
                }
            }
        }
        return res;
}
}
// in this i have iterated for every column and then for every string
// i have used array arr[101] in order to store wich indices are valid and which are not
// i have taken an array of positions(vector) done[101] to find at which previous locations i found this particular (jth index string ) to be smaller than its successor

class Solution {
public:
     int arr[101]={0}; // arr is to check which columns are valid(0) and invalid(-1)
    vector<int> done[101]; // where u found string j was greater than string j+1 ,u put it into vector

 // below is a helper function in order to check all the locations (at which string j has been classified as done ) are still present or not
    bool check(vector<int>& a){
      for(int i:a){
          if(arr[i]!=-1){
              return 1;
          }
      }
        return 0;
    }
int minDeletionSize(vector<string>& strs) {

        int ans=0;
// for iterating columns
     for(int i=0;i<strs[0].size();i++){
   // for iterating the strings
         for(int j=0;j<strs.size()-1;j++){

           if((done[j].size()==0 || check(done[j])==0) && strs[j][i]>strs[j+1][i]){

                ans++;
               arr[i]=-1; // make the column invalid
                break;
            }
             if(strs[j][i]<strs[j+1][i]){

                 done[j].push_back(i); // here we are storing at which index (i) said string j is ok
             }
         }

     }

        return ans;
    }

};
var minDeletionSize = function(strs) {
    const length = strs.length;
    let inOrder = true, count = 0, deleteIndex = 0;
    while(strs[0].length > 0) {
        inOrder = true;
        for(let i=0; i<length; i++) {
            if(strs[i] > strs[i+1]) {
                inOrder = false;
                for(let index = 0; index<strs[i].length;index++) {
                    if(strs[i][index] > strs[i+1][index]) {
                        deleteIndex = index;
                        break;
                    }
                }
            }
        }
        for(let i=0; i<length; i++) {
            strs[i] = strs[i].substring(0,deleteIndex) + strs[i].substring(deleteIndex+1);
        }
        if(inOrder) {
            break;
        } 
        else {
            count++;
        }
    }
    return count;    
};
Delete Columns to Make Sorted II