Leetcode daily # 14.04.2023

516. Longest Palindromic Subsequence

[516. Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/description/) medium

[blog post](https://leetcode.com/problems/longest-palindromic-subsequence/solutions/3415189/kotlin-dp/)

fun longestPalindromeSubseq(s: String): Int {
    // b + abcaba
    // b + ab_ab_
    // b + a_cab_
    // acbbc + a -> [acbbc]a x[from]==x[to]?1 + p[from+1][to-1]
    val p = Array(s.length) { Array(s.length) { 0 } }
    for (i in s.lastIndex downTo 0) p[i][i] = 1
    for (from in s.lastIndex - 1 downTo 0)
    for (to in from + 1..s.lastIndex)
    p[from][to] = if (s[from] == s[to]) {
        2 + if (to == from + 1) 0 else p[from + 1][to - 1]
    } else {
        maxOf(p[from][to - 1], p[from + 1][to])
    }
    return p[0][s.lastIndex]
}

#### Join me on Telegram

https://t.me/leetcode_daily_unstoppable/180

#### Intuition

Simple DFS would not work as it will take $$O(2^n)$$ steps.

Consider the sequence: `acbbc` and a new element `a`. The already existing largest palindrome is `cbbc`. When adding a new element, we do not care about what is inside between `a..a`, just the largest value of it.

So, there is a DP equation derived from this observation: $$p[i][j] = eq ? 2 + p[i+1][j-1] : max(p[i][j-1], p[i+1][j])$$.

#### Approach

For cleaner code:

* precompute `p[i][i] = 1`

* exclude `0` and `lastIndex` from iteration

* start with `to = from + 1`

#### Complexity

- Time complexity:

$$O(n^2)$$

- Space complexity:

$$O(n^2)$$