Leetcode daily # 22.04.2023

[1312. Minimum Insertion Steps to Make a String Palindrome]

22.04.2023

1312. Minimum Insertion Steps to Make a String Palindrome hard

fun minInsertions(s: String): Int {
    // abb -> abba
    // abb*
    //  ab -> aba / bab
    // *ab
    //  bba -> abba
    // *bba
    //   bbbaa -> aabbbaa
    // **bbbaa
    //    bbbcaa -> aacbbbcaa
    // ***bbbcaa
    // leetcode ->  leetcodocteel
    // leetcod***e**
    //      o -> 0
    //      od -> dod / dod -> 1
    //     cod -> codoc / docod -> 2
    //     code -> codedoc / edocode -> 2+1=3
    //    tcod -> tcodoct / doctcod -> 2+1=3
    //    tcode -> tcodedoct / edoctcode -> 3+1=4
    //   etcode = e{tcod}e -> e{tcodoct / doctcod}e -> 3
    //   etcod -> 1+{tcod} -> 1+3=4
    //  eetcod -> docteetcod 4 ?/ eetcodoctee 5
    //  eetcode -> edocteetcode 5 / eetcodedoctee 6 -> e{etcod}e 4 = e{etcodocte}e
    // leetcod -> 1+{eetcod} -> 5
    // leetcode -> 1+{eetcode} 1+4=5
    // aboba
    // a -> 0
    // ab -> 1
    // abo -> min({ab}+1, 1+{bo}) =2
    // abob -> min(1+{bob}, {abo} +1)=1
    // aboba -> min(0 + {bob}, 1+{abob}, 1+{boba}) = 0
    val cache = mutableMapOf<Pair<Int, Int>, Int>()
    fun dfs(from: Int, to: Int): Int {
        if (from > to || from < 0 || to > s.lastIndex) return -1
        if (from == to) return 0
        if (from + 1 == to) return if (s[from] == s[to]) 0 else 1
        return cache.getOrPut(from to to) {
            if (s[from] == s[to]) return@getOrPut dfs(from + 1, to - 1)
            val one = dfs(from + 1, to)
            val two = dfs(from, to - 1)
            when {
                one != -1 && two != -1 -> 1 + minOf(one, two)
                one != -1 -> 1 + one
                two != -1 -> 1 + two
                else -> -1
            }
        }
    }
    return dfs(0, s.lastIndex)
}

blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/188

Intuition

Let’s add chars one by one. Single char is a palindrome. Two chars are palindrome if they are equal, and not if not:

\(insertions_{ab} =\begin{cases} 0, & \text{if a==b}\\ 1 \end{cases}\)

While adding a new character, we choose the minimum insertions. For example, aboba:

// aboba
// a -> 0
// ab -> 1
// abo -> min({ab}+1, 1+{bo}) =2
// abob -> min(1+{bob}, {abo} +1)=1
// aboba -> min(0 + {bob}, 1+{abob}, 1+{boba}) = 0

So, the DP equation is the following dpi,j=min(0+dpi+1,j−1,1+dpi+1,j,1+dpi,j−1dpi,j​=min(0+dpi+1,j−1​,1+dpi+1,j​,1+dpi,j−1​, where DP - is the minimum number of insertions.

Approach

Just DFS and cache.

Complexity

• Time complexity:
  O(n2)

• Space complexity:
  O(n2)