[LeetCode][Kotlin] 2002. Maximum Product of the Length of Two Palindromic Subsequences

2002. Maximum Product of the Length of Two Palindromic Subsequences

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.

 

Return the maximum possible product of the lengths of the two palindromic subsequences.

 

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.

문자열 s가 주어지면 길이의 곱이 최대가 되는 s의 분리된 회문 부분 수열 두 개를 찾습니다. 두 하위 시퀀스가 ​​모두 동일한 인덱스에서 문자를 선택하지 않으면 연결되지 않습니다. 

두 개의 회문 부분 수열 길이의 가능한 최대 곱을 반환합니다. 

하위 시퀀스는 나머지 문자의 순서를 변경하지 않고 일부 문자를 삭제하거나 문자를 전혀 삭제하지 않고 다른 문자열에서 파생될 수 있는 문자열입니다. 문자열을 앞뒤로 읽으면 회문형입니다.

 

Example 1:

Input: s = "leetcodecom"

Output: 9

Explanation: An optimal solution is to choose "ete" for the 1st subsequence and "cdc" for the 2nd subsequence.

The product of their lengths is: 3 * 3 = 9.

 

Example 2:

Input: s = "bb"

Output: 1

Explanation: An optimal solution is to choose "b" (the first character) for the 1st subsequence and "b" (the second character) for the 2nd subsequence.

The product of their lengths is: 1 * 1 = 1.

 

Example 3:

Input: s = "accbcaxxcxx"

Output: 25

Explanation: An optimal solution is to choose "accca" for the 1st subsequence and "xxcxx" for the 2nd subsequence.

The product of their lengths is: 5 * 5 = 25.

 

Constraints:

• 2 <= s.length <= 12
• s consists of lowercase English letters only.

---

코드

• 모든 가능한 부분 수열을 생성하기 위해 비트 마스크를 사용한다.
• 생성된 부분 수열이 회문인지 확인한다. 회문이면 해당 부분 수열의 길이를 저장한다.
• 두 개의 회문 부분 수열 길이의 가능한 최대 곱을 반환한다.

class Solution {
    fun maxProduct(s: String): Int {
        val N = s.length
        val hm = HashMap<Int, Int>()

        for (mask in 1 until (1 shl N)) {
            var subseq = ""
            for (i in 0 until N) {
                if (mask and (1 shl i) != 0) {
                    subseq += s[i]
                }
            }

            if (subseq == subseq.reversed()) {
                hm[mask] = subseq.length
            }
        }

        var res = 0
        for (m1 in hm.keys) {
            for (m2 in hm.keys) {
                if (m1 and m2 == 0) {
                    res = maxOf(res, hm[m1]!! * hm[m2]!!)
                }
            }
        }

        return res
    }
}