LeetCode Entry

1653. Minimum Deletions to Make String Balanced

30.07.2024 medium 2024 kotlin rust

Min removals to sort 'ab' string

1653. Minimum Deletions to Make String Balanced medium blog post substack youtube 2024-07-30_08-26_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/686

Problem TLDR

Min removals to sort ‘ab’ string #medium

Intuition

Let’s try every i position and count how many b are on the left and how many a on the right side.

Another solution is a clever one: we count every b that is left to the a and remove it. For situations like bba where we should remove a this also works, as we remove one position of the incorrect order.

Approach

Let’s implement first solution in Kotlin and second in Rust.

  • as we count bl at the current position, we should consider corner case of countA removals

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


    fun minimumDeletions(s: String): Int {
        val countA = s.count { it == 'a' }; var bl = 0
        return min(countA, s.indices.minOf {
            if (s[it] == 'b') bl++
            bl + (countA - it - 1 + bl)
        })
    }



    pub fn minimum_deletions(s: String) -> i32 {
        let (mut bl, mut del) = (0, 0);
        for b in s.bytes() {
            if b == b'b' { bl += 1 }
            else if bl > 0 { del += 1; bl -= 1 }
        }; del
    }