Maximum Product of the Length of Two Palindromic Subsequences — LeetCode 2002 Python Solution
MediumBit ManipulationStringDynamic ProgrammingBacktrackingBitmask
- Problem
- #2002
- Pattern
- Backtracking
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- s = "leetcodecom"
- Output
- 9
- Explanation
- An optimal solution is to choose "ete" for the 1st subsequence and "cdc" for the 2nd subsequence.
Python solution
Python
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
p = [True] * (1 << n)
for k in range(1, 1 << n):
i, j = 0, n - 1
while i < j:
while i < j and (k >> i & 1) == 0:
i += 1
while i < j and (k >> j & 1) == 0:
j -= 1
if i < j and s[i] != s[j]:
p[k] = False
break
i, j = i + 1, j - 1
ans = 0
for i in range(1, 1 << n):
if p[i]:
mx = ((1 << n) - 1) ^ i
j = mx
a = i.bit_count()
while j:
if p[j]:
b = j.bit_count()
ans = max(ans, a * b)
j = (j - 1) & mx
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | (2^n \times n + 3^n) |
| Space | O(2^n) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences?
- LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences?
- The Python solution on this page runs in (2^n \times n + 3^n).
- What is the space complexity of LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences?
- The Python solution on this page uses O(2^n) auxiliary space.
- What topics does LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences cover?
- LeetCode 2002. Maximum Product of the Length of Two Palindromic Subsequences is tagged Bit Manipulation, String, Dynamic Programming, Backtracking and Bitmask on LeetCode.