DFS Solution 1 ms Java
I don\'t see a dfs solution. Essentially, the idea is to visit each column and look at \'ranges\' of indices within the column where the characters are the same
I don\'t see a dfs solution. Essentially, the idea is to visit each column and look at \'ranges\' of indices within the column where the characters are the same. Then you go to the next column at look at that range. This turns out to be O(MN) time as you are only visiting each character once if at all.\n\nSo for example:\n["ayg","abu","bsv","btr"]\nFirst we would visit the first column and find out that two a\'s occur in a row. This would be treated as a \'range\', then in the next column we would look at the range where we had the two a\'s from before, realize that they are out of order, but continue to the next column using the same range as before. We would do the same thing with the rows that start with \'b\', and discover that the last two chars in the \'b\' rows are out of order, and thus that column is now invalid. You would continue and build \'sub-ranges\' successively if there are more groups of similar characters within ranges.\n\nInitially, this failed on the very last test case (["vdy","vei","zvc","zld"]), which made me think that dfs does not work for a minute. It will essentially fail by calculating column 1 as invalid per the rows that start with \'z\'. Yet since column 1 is invalid, column 2 for the rows that start with \'v\' must also be explored instead of being ignored (it is ignored since \'d\' and \'e\' in the \'v\' rows were in order and were not the same letters). \n\nBut it turns out, if you run dfs twice, the algorithm will work. This is because it will reconcile any columns that were marked as invalid by later ranges of strings. But weren\'t taken into account for earlier ranges of strings which may have considered that particular column as valid. \n\nOverall this is O(MN) time as you are really only visiting each character at most once (or possibly just visiting the column that the character is in). And it is O(M) extra space.\n\n```\nclass Solution {\n    public int minDeletionSize(String[] strs) {\n        Set<Integer> invalidCols = new HashSet<>();\n        dfs(0, strs.length-1, 0, strs, invalidCols); // Initial run\n        dfs(0, strs.length-1, 0, strs, invalidCols); // Reconciliation run\n        return invalidCols.size();\n    }\n    protected void dfs(int start, int end, int col, String [] strs, Set<Integer> invalidCols){\n        int currCnt = 0;\n        if(col == strs[0].length()){\n            return;\n        }\n        if(invalidCols.contains(col)){\n            dfs(start, end, col+1, strs, invalidCols); // Continue as to check the next column. No need to check the range of chars for this column.\n            return;\n        }\n        for(int i=start+1;i<=end;i++){\n            if(strs[i].charAt(col) < strs[i-1].charAt(col)){\n                invalidCols.add(col);\n                dfs(start, end, col+1, strs, invalidCols); // Check the same previous range of characters in the next column as this column is now invalid\n                return;\n            }\n        }\n        int startIndex = start;\n        for(int i=start+1;i<=end;i++){\n            if(strs[i].charAt(col) != strs[i-1].charAt(col)){\n                if(i-startIndex > 1){\n                    dfs(startIndex, i-1, col+1, strs, invalidCols); // Check this range of characters that are the same\n                }\n                startIndex = i;\n            }\n        }\n        if(end - startIndex >= 1){\n            dfs(startIndex, end, col+1, strs, invalidCols); // Check this range of characters that are the same\n        }\n    }\n}\n```
[]