The Longest Palindromic Subsequence II problem asks you to find the length of the longest palindromic subsequence in a given string s, with an additional constraint:
The subsequence must use at least two different characters.
Definitions:
Constraints:
1 <= s.length <= 1000s consists of only lowercase English letters.
Example:
If s = "bbabab", the answer is 5 (for subsequence "babab" or "baab" etc.), but "bbbbbb" would not be valid because it only uses one character.
At first glance, the problem looks similar to the classic Longest Palindromic Subsequence (LPS) problem, which is typically solved using dynamic programming. However, the added requirement that the palindrome must use at least two different characters changes things.
A brute-force approach would be to generate all possible subsequences, check if they are palindromic, and whether they contain at least two different characters. But this is extremely inefficient, as the number of subsequences grows exponentially with the length of the string.
To optimize, we can adapt the standard DP solution for LPS but add a check to ensure that the subsequence contains at least two different characters. This requires us to track more information in our DP state or post-process the results to exclude palindromes made of a single character.
We solve this problem using dynamic programming, building on the standard LPS approach:
dp[i][j] be the length of the longest palindromic subsequence within s[i..j].i, dp[i][i] = 1 (a single character is a palindrome of length 1).s[i] == s[j], then dp[i][j] = 2 + dp[i+1][j-1].dp[i][j] = max(dp[i+1][j], dp[i][j-1]).dp[0][n-1] (as in the classic LPS).s[i..j] where dp[i][j] > 1, check if s[i..j] contains at least two different characters.dp[i][j].Why dynamic programming? Because it avoids recomputation and efficiently explores all possible palindromic subsequences, while the additional check ensures the extra constraint is met.
Example: s = "bbabab"
dp[i][i] = 1.s[i] == s[i+1], dp[i][i+1] = 2.dp[i][j] (where i < j), check if the substring s[i..j] contains at least two different characters.Brute-force Approach:
O(2^n) (generates all subsequences).O(n) (call stack or temporary storage).n up to 1000.O(n^3) (DP is O(n^2), but checking for two different characters in each substring can be O(n) if not optimized; can be reduced with pre-processing or frequency arrays).O(n^2) (for the DP table).
With further optimization (e.g., precomputing prefix character counts), the substring diversity check can be reduced to O(1) per query, making the total time complexity O(n^2 * 26) (still acceptable).
The Longest Palindromic Subsequence II problem extends the classic LPS challenge by requiring at least two different characters in the subsequence. By leveraging dynamic programming and augmenting it with a diversity check, we can efficiently find the solution even for large strings. The key insight is to adapt the standard DP approach and ensure that the palindrome is not composed of a single repeated character, using additional data structures or pre-processing as needed.
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0]*n for _ in range(n)]
# Precompute prefix character counts for diversity check
prefix = [[0]*26 for _ in range(n+1)]
for i in range(n):
for c in range(26):
prefix[i+1][c] = prefix[i][c]
prefix[i+1][ord(s[i])-ord('a')] += 1
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n-length+1):
j = i+length-1
if s[i] == s[j]:
dp[i][j] = 2 + (dp[i+1][j-1] if i+1 <= j-1 else 0)
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
maxlen = 0
for i in range(n):
for j in range(i+1, n):
if dp[i][j] > 1:
# Check if substring s[i..j] contains at least two different characters
diff = 0
for c in range(26):
if prefix[j+1][c] - prefix[i][c] > 0:
diff += 1
if diff >= 2:
break
if diff >= 2:
maxlen = max(maxlen, dp[i][j])
return maxlen
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
vector<vector<int>> prefix(n+1, vector<int>(26, 0));
for (int i = 0; i < n; ++i) {
for (int c = 0; c < 26; ++c)
prefix[i+1][c] = prefix[i][c];
prefix[i+1][s[i]-'a']++;
}
for (int i = 0; i < n; ++i)
dp[i][i] = 1;
for (int length = 2; length <= n; ++length) {
for (int i = 0; i + length - 1 < n; ++i) {
int j = i + length - 1;
if (s[i] == s[j])
dp[i][j] = 2 + ((i+1 <= j-1) ? dp[i+1][j-1] : 0);
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
int maxlen = 0;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
if (dp[i][j] > 1) {
int diff = 0;
for (int c = 0; c < 26; ++c) {
if (prefix[j+1][c] - prefix[i][c] > 0)
diff++;
if (diff >= 2) break;
}
if (diff >= 2)
maxlen = max(maxlen, dp[i][j]);
}
}
}
return maxlen;
}
};
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
int[][] prefix = new int[n+1][26];
for (int i = 0; i < n; i++) {
for (int c = 0; c < 26; c++)
prefix[i+1][c] = prefix[i][c];
prefix[i+1][s.charAt(i) - 'a']++;
}
for (int i = 0; i < n; i++)
dp[i][i] = 1;
for (int length = 2; length <= n; length++) {
for (int i = 0; i + length - 1 < n; i++) {
int j = i + length - 1;
if (s.charAt(i) == s.charAt(j))
dp[i][j] = 2 + ((i+1 <= j-1) ? dp[i+1][j-1] : 0);
else
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
int maxlen = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (dp[i][j] > 1) {
int diff = 0;
for (int c = 0; c < 26; c++) {
if (prefix[j+1][c] - prefix[i][c] > 0)
diff++;
if (diff >= 2) break;
}
if (diff >= 2)
maxlen = Math.max(maxlen, dp[i][j]);
}
}
}
return maxlen;
}
}
var longestPalindromeSubseq = function(s) {
const n = s.length;
const dp = Array.from({length: n}, () => Array(n).fill(0));
const prefix = Array.from({length: n+1}, () => Array(26).fill(0));
for (let i = 0; i < n; ++i) {
for (let c = 0; c < 26; ++c)
prefix[i+1][c] = prefix[i][c];
prefix[i+1][s.charCodeAt(i) - 97]++;
}
for (let i = 0; i < n; ++i)
dp[i][i] = 1;
for (let length = 2; length <= n; ++length) {
for (let i = 0; i + length - 1 < n; ++i) {
let j = i + length - 1;
if (s[i] === s[j])
dp[i][j] = 2 + ((i+1 <= j-1) ? dp[i+1][j-1] : 0);
else
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
let maxlen = 0;
for (let i = 0; i < n; ++i) {
for (let j = i+1; j < n; ++j) {
if (dp[i][j] > 1) {
let diff = 0;
for (let c = 0; c < 26; ++c) {
if (prefix[j+1][c] - prefix[i][c] > 0)
diff++;
if (diff >= 2) break;
}
if (diff >= 2)
maxlen = Math.max(maxlen, dp[i][j]);
}
}
}
return maxlen;
};