Условие

Дан массив строк strs, каждая из которых имеет одинаковую длину. Требуется определить минимальное количество столбцов, которые нужно удалить, чтобы оставшиеся столбцы были лексикографически отсортированы по строкам.

Примеры

Input: strs = ["cba","daf","ghi"] Output: 1 Explanation: Удаление 1-го столбца даст ["ba", "af", "hi"], что является отсортированным.

Input: strs = ["a","b"] Output: 0 Explanation: Все столбцы уже отсортированы.

Input: strs = ["zyx","wvu","tsr"] Output: 3 Explanation: Необходимо удалить все 3 столбца.

Решение

fun minDeletionSize(strs: Array<String>): Int {
    val numRows = strs.size
    val numCols = strs[0].length
    var deletions = 0

    // Проход по каждому столбцу
    for (col in 0 until numCols) {
        for (row in 0 until numRows - 1) {
            // Если обнаружено несоответствие, увеличиваем счетчик удалений
            if (strs[row][col] > strs[row + 1][col]) {
                deletions++
                break
            }
        }
    }

    return deletions
}

Временная сложность

O(n * m), где n — количество строк, m — длина строки.

Пространственная сложность

O(1), поскольку используется только пара переменных для хранения размеров и счетчика.