educative.io

Educative

Recursive solution for interested folks


private fun longestPalindromeSubsequence(st: String, l: Int, r: Int): Int {
        if (l > r) {
            return 0
        }

        if (l == r) {
            return 1
        }

        if (st[l] == st[r]) {
            return 2 + longestPalindromeSubsequence(st, l + 1, r - 1)
        }

        // if the first & last characters don't match continue
        val c1 = longestPalindromeSubsequence(st, l + 1, r)
        val c2 = longestPalindromeSubsequence(st, l, r - 1)

        return max(c1, c2)
    }

    private fun minDeletions(st: String): Int {
        val longestSeq = longestPalindromeSubsequence(st, 0, st.length - 1)
        return st.length - longestSeq
    }

Hi,
Thank you for your contribution. Really appreciate the effort.

Regards