Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Solution Explanation: Longest Palindromic Subsequence

This problem asks to find the length of the longest palindromic subsequence within a given string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A palindrome is a sequence that reads the same backwards as forwards.

The most efficient approach to solve this is using dynamic programming.

Dynamic Programming Approach

We'll create a 2D array dp where dp[i][j] represents the length of the longest palindromic subsequence within the substring s[i...j] (inclusive).

Base Cases:

• dp[i][i] = 1 for all i, because a single character is a palindrome of length 1.

Recursive Relation:

• If s[i] == s[j], it means we've found a potential palindrome. We can extend the palindrome by including s[i] and s[j], and the length will be dp[i+1][j-1] + 2.
• If s[i] != s[j], we can't extend the palindrome using both s[i] and s[j]. We need to consider two possibilities:
  • The longest palindromic subsequence lies within s[i+1...j], so we take dp[i+1][j].
  • The longest palindromic subsequence lies within s[i...j-1], so we take dp[i][j-1]. We choose the maximum of these two possibilities.

Therefore, the recursive relation is:

dp[i][j] = 
  s[i] == s[j] ? dp[i+1][j-1] + 2 : max(dp[i+1][j], dp[i][j-1]) 

Iteration Order:

To avoid dependencies between cells, we iterate through the dp array diagonally, starting from the main diagonal (single characters) and moving towards the top-right corner. This ensures that when we calculate dp[i][j], dp[i+1][j] and dp[i][j-1] have already been computed.

Result:

The final result is stored in dp[0][n-1], where n is the length of the string.

Time and Space Complexity

• Time Complexity: O(n^2) due to the nested loops iterating through the dp array.
• Space Complexity: O(n^2) to store the dp array. We can optimize this to O(n) by using only two rows of the dp array, but the provided solutions use the full array for clarity.

Code Examples (Python, Java, C++, Go, TypeScript)

The code examples provided in the problem description accurately implement this dynamic programming solution. They differ only in syntax according to each language's specifics. Each solution follows the algorithm explained above: initializes the base cases, iterates through the dp table to fill it using the recursive relation and finally returns the result stored at dp[0][n-1].

The code's structure is very similar across all languages, reflecting the algorithm's straightforward nature. The only notable difference is how the 2D array (dp or f) is initialized and accessed using each language's particular syntax. The core logic remains consistent.