LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences

LeetCode Notes [44]

Problem

Maximum Product of the Length of Two Palindromic Subsequences - LeetCode

Approach 1: DFS

Search all possible subsequences using DFS, and then find disjoint subsequences with maximum product of length.

Implementation

class Solution {
    private var candidates = mutableListOf<List<Int>>()
    fun maxProduct(s: String): Int {
        candidates = mutableListOf()
        search(s, listOf(), 0)
        return calculate()
    }

    private fun calculate(): Int {
        var max = Int.MIN_VALUE
        for (i in candidates.indices) {
            val p1 = candidates[i]
            for (j in i + 1 until candidates.size) {
                val p2 = candidates[j]
                if (!p1.any { it in p2 }) {
                    val mul = p1.size * p2.size
                    if (mul > max) {
                        max = mul
                    }
                }
            }
        }
        return max
    }

    private fun search(s: String, list: List<Int>, curIndex: Int) {
        if (curIndex < s.length) {
            val newList = list.toMutableList()
            search(
                s,
                newList.apply { add(curIndex) },
                curIndex + 1
            )
            search(s, list, curIndex + 1)
        } else {
            var result = ""
            list.forEach {
                result += s[it]
            }
            if (isPalindromic(result)) {
                candidates.add(list)
            }
        }
    }

    private fun isPalindromic(s: String): Boolean {
        if (s.isEmpty()) return false
        for (i in 0..s.length / 2) {
            if (s[i] != s[s.length - 1 - i])
                return false
        }
        return true
    }
}

Complexity Analysis

• Time Complexity: O(sigma_0_n(2^n))
• Space Complexity: O(n* 2^n)

Approach 2: Improved DFS

Since for each character c in the given string s, c will be either

• In subsequence1
• In subsequence2
• Neither in subsequence1, nor subsequence2

The recurrence will be:

• If i < s.length,

F(i, s1, s2) = max(
    F(i+1, s1 + c, s2),
    F(i+1, s1, s2 + c),
    F(i+1, s1, s2)
)

• If i == s.length and both s1 and s2 are palindromic, return the product of their length.

Implementation

class Solution {
    private var max = Int.MIN_VALUE

    private fun isPalindromic(s: String): Boolean {
        if (s.isEmpty()) return false
        for (i in 0..s.length / 2) {
            if (s[i] != s[s.length - 1 - i])
                return false
        }
        return true
    }

    fun maxProduct(s: String): Int {
        max = Int.MIN_VALUE
        search(s, 0, "", "")
        return max
    }

    private fun search(s: String, index: Int, s1: String, s2: String) {
        if (index < s.length) {
            search(s, index + 1, s1 + s[index], s2)
            search(s, index + 1, s1, s2 + s[index])
            search(s, index + 1, s1, s2)
        } else {
            if (isPalindromic(s1) && isPalindromic(s2)) {
                val mul = s1.length * s2.length
                if (mul > max) {
                    max = mul
                }
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(sigma_0_n(3^n))
• Space Complexity: O(n)