Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 14

Description

Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s.

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.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

Solution

class Solution {
public:
  int longestPalindromeSubseq(string s) {
    int len = s.length();
    vector<int> dp(len), dp_(len), dp__(len);

    for(int l = 1; l <= len; ++l) {
      for(int i = 0; i < len - l + 1; ++i) {
        int j = i + l - 1;
        if(l == 1) {
          dp[j] = 1;
        } else if(s[i] == s[j]) {
          dp[j] = dp__[j - 1] + 2;
        } else {
          dp[j] = max(dp_[j], dp_[j - 1]);
        }
      }
      swap(dp__, dp_);
      dp_ = dp;
    }
    
    return dp.back();
  }
};

// Accepted
// 86/86 cases passed (80 ms)
// Your runtime beats 88.97 % of cpp submissions
// Your memory usage beats 88.37 % of cpp submissions (6.7 MB)