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.
Solution 1: DFS
Time complexity: O(3n*n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua class Solution { public: int maxProduct(string s) { auto isPalindrom = [](const string& s) { for (int i = 0; i < s.length(); ++i) if (s[i] != s[s.size() - i - 1]) return false; return true; }; const int n = s.size(); vector<string> ss(3); size_t ans = 0; function<void(int)> dfs = [&](int i) -> void { if (i == n) { if (isPalindrom(ss[0]) && isPalindrom(ss[1])) ans = max(ans, ss[0].size() * ss[1].size()); return; } for (int k = 0; k < 3; ++k) { ss[k].push_back(s[i]); dfs(i + 1); ss[k].pop_back(); } }; dfs(0); return ans; } }; |
Solution: Subsets + Bitmask + All Pairs
Time complexity: O(22n)
Space complexity: O(2n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua class Solution { public: int maxProduct(string s) { auto isPalindrom = [](const string& s) { for (int i = 0; i < s.length(); ++i) if (s[i] != s[s.size() - i - 1]) return false; return true; }; const int n = s.size(); unordered_set<int> p; for (int i = 0; i < (1 << n); ++i) { string t; for (int j = 0; j < n; ++j) if (i >> j & 1) t.push_back(s[j]); if (isPalindrom(t)) p.insert(i); } int ans = 0; for (int s1 : p) for (int s2 : p) if (!(s1 & s2)) ans = max(ans, __builtin_popcount(s1) * __builtin_popcount(s2)); return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment