LeetCode Entry

955. Delete Columns to Make Sorted II

21.12.2025 medium 2025 kotlin rust

Remove columns to sort strings

955. Delete Columns to Make Sorted II medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1211

Problem TLDR

Remove columns to sort strings #medium

Intuition

The brute-force works. Build the strings column by column and either accept the current column or not.

Approach

• optimization: keep only rows that have equal chars

Complexity

• Time complexity: \(O(n^3)\) or n^2 optimized

• Space complexity: \(O(n^2)\) or n oprimized

Code

// 32ms
    fun minDeletionSize(s: Array<String>): Int {
        var res = List(s.size) { "" }
        return s[0].indices.count { i ->
            val r = res.zip(s).map { (a,b) -> a + b[i] }
            (1..<s.size).any { r[it-1] > r[it] }.also { if (!it) res = r }
        }
    }

// 0ms
    pub fn min_deletion_size(s: Vec<String>) -> i32 {
        let mut js: Vec<_> = (1..s.len()).collect();
        (0..s[0].len()).filter(|&i| {
            let rm = js.iter().any(|&j| s[j-1].as_bytes()[i] > s[j].as_bytes()[i]);
            if !rm { js.retain(|&j| s[j-1].as_bytes()[i] == s[j].as_bytes()[i]) }; rm
        }).count() as _
    }