LeetCode Entry

712. Minimum ASCII Delete Sum for Two Strings

10.01.2026 medium 2026 kotlin rust

Min removed sum to make strings equal

712. Minimum ASCII Delete Sum for Two Strings medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1233

Problem TLDR

Min removed sum to make strings equal #medium #dp

Intuition

One way: DP[i][j] is the removed sum for suffix a[i..],b[j..], take a[i] or b[j] when a[i]!=b[j].

Second way: DP[i][j] is the Longest Common Substring for suffix a[i..],b[j..], take a[i] when a[i]==b[j].

Approach

• the DFS top-down is easier to write
• space optimize with i%2 trick: only the last row is needed
• forward write to simplify indices dp[i+1][j+1] = … a[i],b[j]

Complexity

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

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

Code

// 30ms
    fun minimumDeleteSum(a: String, b: String): Int {
        val d = Array(2) { IntArray(b.length+1) }
        for (i in a.indices) for (j in b.indices) d[(i+1)%2][j+1] =
            if (a[i] == b[j]) a[i].code + d[i%2][j] else max(d[i%2][j+1], d[(i+1)%2][j])
        return a.sumOf{it.code}+b.sumOf{it.code}-2*d[a.length%2][b.length]
    }

// 3ms
    pub fn minimum_delete_sum(a: String, b: String) -> i32 {
        let (a, b, mut d) = (a.as_bytes(), b.as_bytes(), vec![vec![0; b.len() + 1]; 2]);
        for j in 0..b.len() { d[0][j + 1] = d[0][j] + b[j] as i32 }
        for i in 0..a.len() { for j in 0..=b.len() { d[(i + 1) & 1][j] =
            if j < 1 { d[i & 1][0] + a[i] as i32 } else if a[i] == b[j - 1] { d[i & 1][j - 1] }
            else { (a[i] as i32 + d[i & 1][j]).min(b[j - 1] as i32 + d[(i + 1) & 1][j - 1]) }
        }}
        d[a.len() & 1][b.len()]
    }