Maximum Product of the Length of Two Palindromic Subsequences
MedPrompt
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.
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 <= 12sconsists of lowercase English letters only.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating all possible subsequences of the input string s, checking which ones are palindromic, and then finding the best pair of disjoint palindromic subsequences by checking all pairs.
Algorithm
- Initialize
n = s.length(). - Create a map
palindromesto store(mask, length)for palindromic subsequences. - Iterate
maskfrom1to(1 << n) - 1:- Construct the subsequence
subfromsusingmask. - If
subis a palindrome, put(mask, sub.length())intopalindromes.
- Construct the subsequence
- Initialize
maxProduct = 0. - Convert the keys of
palindromesinto a listpMasks. - Iterate through all pairs
(mask1, mask2)frompMasks:- If
(mask1 & mask2) == 0(the subsequences are disjoint):product = palindromes.get(mask1) * palindromes.get(mask2).maxProduct = max(maxProduct, product).
- If
- Return
maxProduct.
Walkthrough
- Generate all subsequences: We can represent each subsequence using a bitmask of length
n(wherenis the length ofs). A '1' at thei-th position in the mask means the characters.charAt(i)is included in the subsequence. We iterate through all2^npossible masks. - Identify palindromic subsequences: For each mask, we construct the corresponding subsequence string. We then check if this string is a palindrome.
- Store palindromes: We store the masks of all palindromic subsequences and their lengths, for example, in a hash map where the key is the mask and the value is the length.
- Find the best pair: After identifying all palindromic subsequences, we iterate through all possible pairs of them. For each pair, we check if their corresponding masks are disjoint (i.e., their bitwise AND is zero). If they are disjoint, we calculate the product of their lengths and update our maximum product found so far.
class Solution { public int maxProduct(String s) { int n = s.length(); Map<Integer, Integer> palindromeLengths = new HashMap<>(); for (int mask = 1; mask < (1 << n); mask++) { StringBuilder sub = new StringBuilder(); for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) { sub.append(s.charAt(i)); } } if (isPalindrome(sub.toString())) { palindromeLengths.put(mask, sub.length()); } } int maxProd = 0; List<Integer> masks = new ArrayList<>(palindromeLengths.keySet()); for (int i = 0; i < masks.size(); i++) { for (int j = i; j < masks.size(); j++) { int mask1 = masks.get(i); int mask2 = masks.get(j); if ((mask1 & mask2) == 0) { int product = palindromeLengths.get(mask1) * palindromeLengths.get(mask2); maxProd = Math.max(maxProd, product); } } } return maxProd; } private boolean isPalindrome(String str) { int left = 0, right = str.length() - 1; while (left < right) { if (str.charAt(left) != str.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
O(n * 2^n + P^2), where P is the number of palindromic subsequences. In the worst case, P can be close to 2^n, making the complexity O(n * 2^n + 4^n). For n=12, this is computationally expensive.
Space
O(P), where P is the number of palindromic subsequences. In the worst case, this can be O(2^n) to store the masks and lengths.
Trade-offs
Pros
Conceptually straightforward extension of generating all subsequences.
Cons
The pairwise check can be very slow if there are many palindromic subsequences, leading to a high time complexity that might not pass for larger constraints.
Solutions
Solution
class Solution {public int maxProduct(String s) { int n = s.length(); boolean[] p = new boolean[1 << n]; Arrays.fill(p, true); for (int k = 1; k < 1 << n; ++k) { for (int i = 0, j = n - 1; i < n; ++i, --j) { while (i < j && (k >> i & 1) == 0) { ++i; } while (i < j && (k >> j & 1) == 0) { --j; } if (i < j && s.charAt(i) != s.charAt(j)) { p[k] = false; break; } } } int ans = 0; for (int i = 1; i < 1 << n; ++i) { if (p[i]) { int a = Integer.bitCount(i); int mx = ((1 << n) - 1) ^ i; for (int j = mx; j > 0; j = (j - 1) & mx) { if (p[j]) { int b = Integer.bitCount(j); ans = Math.max(ans, a * b); } } } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.