Track if so far constructed substrings are equal
Intuition\n\nLet\'s say we build a substring by removing letters that cause substrings to not be lexicographically sorted. This substring is not a contiguous pa
# Intuition\n\nLet\'s say we build a substring by removing letters that cause substrings to not be lexicographically sorted. This substring is not a contiguous part of input string.\n\nAs mentioned even in the description, `strs[0][1]` doesn\'t need to be smaller than `strs[1][1]`. It may be greater as long as so far built substrings are not equal (we don\'t use a character if it results in substring 1 being smaller than substring 0, that\'s why we can just track equality).\n\nFor example with `abcd` and `abcc`, column 3 (0-indexed) breaks the order, but with `abcd` and `azcc` strings are still lexographically sorted.\n\n# Approach\n\nCreate a vector of bool indicating if a substring is equal to the previous substring and initialize all to true, as all empty substrings are equal.\n\nFor each column:\n- Iterate through all strings. If a letter at given column is smaller than the letter from the previous string, check if the substrings are equal. If they are, this letter breaks the order, so the column should be removed. If they aren\'t, then this letter doesn\'t change the order anyway.\n- If the column may be used, iterate through all strings again and update the `eq_with_prev` vector.\n\nTracking if the substrings are equal may possibly be optimized, but it won\'t change the time complexity anyway.\n\n# Complexity\n- Time complexity:\nO(n*m), where n - number of strings, m - length of the string\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int minDeletionSize(vector<string>& strs) {\n        const int len = strs[0].size();\n        const int num_strs = strs.size();\n        int result = 0;\n        vector<bool> eq_with_prev(num_strs, true);\n\n        for (int col = 0; col < len; col++) {\n            int i = 1;\n            for (; i < num_strs; i++) {\n                if (strs[i][col] < strs[i - 1][col] && eq_with_prev[i]) {\n                    result++;\n                    break;\n                }\n            }\n\n            if (i == num_strs) {\n                for (int j = 1; j < num_strs; j++) {\n                    if (strs[j][col] != strs[j - 1][col]) {\n                        eq_with_prev[j] = false;\n                    }\n                }\n            }\n        }\n\n        return result;\n    }\n};\n```
['C++']