grid47 Exploring patterns and algorithms
Sep 16, 2024
6 min read
Solution to LeetCode 516: Longest Palindromic Subsequence Problem
Given a string s, return the length of the longest palindromic subsequence in s. A subsequence is a sequence derived by deleting some or no elements without changing the order of the remaining elements.
Problem
Approach
Steps
Complexity
Input: The input is a string `s` consisting of lowercase English letters.
Example: s = "aabca"
Constraints:
• 1 <= s.length <= 1000
• s consists only of lowercase English letters.
Output: The output should be an integer representing the length of the longest palindromic subsequence in `s`.
Example: 3
Constraints:
• The output should be a single integer.
Goal: To find the length of the longest subsequence in `s` that is a palindrome.
Steps:
• 1. Use dynamic programming to store intermediate results.
• 2. For each pair of indices `i` and `j`, check if the characters match.
• 3. If the characters match, consider the longest subsequence between `i+1` and `j-1`, and add 2.
• 4. If the characters don't match, take the maximum value between `dp(i + 1, j)` and `dp(i, j - 1)`.
Goal: The string `s` will be between 1 and 1000 characters long, and will only contain lowercase letters.
Steps:
• 1 <= s.length <= 1000
• s consists only of lowercase English letters.
Assumptions:
• The string `s` is not empty unless specified.
• The input string contains only lowercase English letters.
• Input: s = "aabca"
• Explanation: The longest palindromic subsequence in the string 'aabca' is 'aba', which has a length of 3.
• Input: s = "abcde"
• Explanation: Since no characters repeat, the longest palindromic subsequence is any single character, with a length of 1.
Approach: The approach uses dynamic programming to calculate the longest palindromic subsequence.
Observations:
• Dynamic programming is an effective way to store and reuse previously computed results.
• The solution needs to compare characters from the string and compute intermediate results for subsequences.
• We can use a table to store the lengths of palindromic subsequences for different indices in the string.
Steps:
• 1. Initialize a 2D array `dp` where `dp[i][j]` represents the length of the longest palindromic subsequence in the substring from index `i` to `j`.
• 2. Iterate over all pairs of indices `i` and `j` and fill the `dp` array using the recurrence relation.
• 3. The value of `dp[0][n-1]` will contain the length of the longest palindromic subsequence of the entire string `s`.
Empty Inputs:
• If the string is empty, the longest palindromic subsequence length is 0.
Large Inputs:
• The algorithm should efficiently handle strings with lengths up to 1000 characters.
Special Values:
• If all characters in the string are the same, the entire string is a palindrome.
Constraints:
• The string length should be between 1 and 1000.
string str;
vector<vector<int>> memo;
intdp(int i, int j) {
if(i == j) return1;
if(i == j -1) return str[i] == str[j]?2:1;
if(memo[i][j] !=-1) return memo[i][j];
int ans =0;
if(str[i] == str[j]) {
ans =2+ dp(i +1, j -1);
} else {
ans = max(dp(i +1, j), dp(i, j -1));
}
return memo[i][j] = ans;
}
intlongestPalindromeSubseq(string s) {
str = s;
int n = s.size();
memo.resize(n, vector<int>(n, -1));
return dp(0, n -1);
}
1 : String Initialization
string str;
Declares a string variable `str` that will store the input string for the longest palindromic subsequence problem.
2 : Memoization Table Initialization
vector<vector<int>> memo;
Declares a 2D vector `memo` to store the intermediate results of subproblems. This table will help avoid redundant calculations by storing already computed values.
3 : Recursive Function Definition
intdp(int i, int j) {
Defines the recursive function `dp`, which takes two indices `i` and `j` and returns the length of the longest palindromic subsequence between the substring `str[i...j]`.
4 : Base Case 1
if(i == j) return1;
Base case: If the indices `i` and `j` point to the same character, the longest palindromic subsequence has length 1.
5 : Base Case 2
if(i == j -1) return str[i] == str[j]?2:1;
Base case: If `i` and `j` are adjacent characters, the longest palindromic subsequence is 2 if the characters match, otherwise it is 1.
6 : Memoization Check
if(memo[i][j] !=-1) return memo[i][j];
Checks if the result for the substring `str[i...j]` has already been computed and stored in the `memo` table. If yes, returns the cached result.
7 : Recursive Calculation Initialization
int ans =0;
Initializes a variable `ans` to store the result of the longest palindromic subsequence for the current substring `str[i...j]`.
8 : Matching Characters Case
if(str[i] == str[j]) {
Checks if the characters at indices `i` and `j` are equal. If they are, the subsequence can be extended by 2, along with the result of the remaining substring.
9 : Recursive Call for Matching Characters
ans =2+ dp(i +1, j -1);
If the characters match, the longest palindromic subsequence increases by 2 (including the matching characters), and the recursive function is called for the substring `str[i+1...j-1]`.
10 : Non-Matching Characters Case
} else {
Handles the case where the characters at indices `i` and `j` do not match.
11 : Recursive Call for Non-Matching Characters
ans = max(dp(i +1, j), dp(i, j -1));
If the characters do not match, the longest palindromic subsequence is the maximum of the results of the two possible substrings: `str[i+1...j]` and `str[i...j-1]`.
12 : Memoization Step
return memo[i][j] = ans;
Stores the computed result `ans` in the `memo` table to reuse it in future calls.
13 : Main Function Definition
intlongestPalindromeSubseq(string s) {
Defines the main function `longestPalindromeSubseq`, which takes the input string `s` and returns the length of the longest palindromic subsequence.
14 : Assign Input String
str = s;
Assigns the input string `s` to the global string `str` used in the recursive function.
15 : Initialize Memoization Table
int n = s.size();
Calculates the length `n` of the input string `s`.
16 : Resize Memoization Table
memo.resize(n, vector<int>(n, -1));
Resizes the `memo` table to store results for all substrings of length `n`. Initially, all values are set to `-1`, indicating that they have not been computed yet.
17 : Final Recursive Call
returndp(0, n -1);
Makes the first call to the `dp` function to compute the longest palindromic subsequence for the entire string `s`.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is O(n^2) due to the need to compute all pairs of indices in the string.
Best Case: O(n^2)
Worst Case: O(n^2)
Description: The space complexity is O(n^2) due to the storage of the dynamic programming table.
