LeetCode 516. Longest Palindromic Subsequence

LeetCode Notes [45]

Problem

Longest Palindromic Subsequence - LeetCode

Intuition

A string is palindromic if it reads the same forward and backward. Thus, we can simply calculate the Longest Common Subsequence between the original string and the reversed one.

Implementation

import kotlin.math.max

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val s2 = s.reversed()
        val array = Array(s.length + 1) {
            IntArray(s.length + 1) { 0 }
        }
        for (i in 1..s.length) {
            for (j in 1..s.length) {
                if (s[i - 1] == s2[j - 1]) {
                    array[i][j] = array[i - 1][j - 1] + 1
                } else {
                    array[i][j] = max(array[i - 1][j], array[i][j - 1])
                }
            }
        }
        return array[s.length][s.length]
    }
}

Complexity Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n²)