LeetCode Entry

712. Minimum ASCII Delete Sum for Two Strings

31.07.2023 medium 2023 kotlin

Minimum removed chars sum to make strings equal

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

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/292

Problem TLDR

Minimum removed chars sum to make strings equal

Intuition

This is a known Dynamic Programming problem about the minimum edit distance. We can walk both strings and at each time choose what char to take and what to skip. The result is dependent only from the arguments, so can be cached.

Approach

Let’s use DFS and memo.

Complexity

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

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

Code


    fun minimumDeleteSum(s1: String, s2: String): Int {
      val cache = mutableMapOf<Pair<Int, Int>, Int>()
      fun dfs(p1: Int, p2: Int): Int = cache.getOrPut(p1 to p2) { when {
        p1 == s1.length && p2 == s2.length -> 0
        p1 == s1.length -> s2.drop(p2).map { it.toInt() }.sum()!!
        p2 == s2.length -> s1.drop(p1).map { it.toInt() }.sum()!!
        s1[p1] == s2[p2] -> dfs(p1 + 1, p2 + 1)
        else -> minOf(s1[p1].toInt() + dfs(p1 + 1, p2), s2[p2].toInt() + dfs(p1, p2 + 1))
      } }
      return dfs(0, 0)
    }