Find length of longest palindromic subsequence in string s.
Input: s="bbbab" → Output: 4. "bbbb" is the longest palindromic subsequence.
Input: s="cbbd" → Output: 2
DP: dp[i][j] = LPS of s[i..j]. If s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2, else max of dp[i+1][j] and dp[i][j-1].
- dp[i][j] = LPS length of s[i..j]
- Base: dp[i][i] = 1
- Fill diagonally: if s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2
- Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- Return dp[0][n-1]
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][n-1];
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)