Longest Palindromic Subsequence 1 - Get Length

Problem

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.

Examples

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".

Similar Problems

[Longest Palindromic Subsequence - Get Subsequence](longest-palindromic-subsequence-get-subsequence) [Longest Palindromic Subsequence II](longest-palindromic-subsequence-ii)

Solution

This problem will be very similar to [Longest Common Subsequence](longest-common-subsequence-lcs-1-get-length).

A palindromic sequence means a sequence of characters which is a palindrome. Now, we must understand it clearly that we are talking about a sub sequence and not a substring. More: [Subarrays vs Subsequences vs Subsets Definition](subarrays-vs-subsequences-vs-subsets-definition).

It is really easy to say if a string is a palindrome. We have seen it here: [Check if given string is palindrome or not](check-if-given-string-is-palindrome-or-not).

Method 1 - Naive

The brute-force approach is to enumerate every possible subsequence and check which ones are palindromic, then return the length of the longest. Since there are about 2^N subsequences for a string of length N, this method is exponential in time and quickly becomes infeasible for large inputs.

Method 2 – Recursion

Intuition

We can solve this problem recursively by considering the two ends of the string. If the characters at both ends match, they can be part of the palindrome, and we look for the longest palindromic subsequence in the substring between them. If they don't match, we try both possibilities—excluding either end—and take the maximum.

Approach

1. Define a recursive function lps(s, i, j) that returns the length of the longest palindromic subsequence in the substring from index i to j.
2. If i == j, the substring is a single character, so return 1.
3. If s[i] == s[j] and i + 1 == j, return 2 (two matching characters).
4. If s[i] == s[j], return 2 + lps(s, i+1, j-1).
5. Otherwise, return max(lps(s, i+1, j), lps(s, i, j-1)).

Code

C++

class Solution {
public:
    int longestPalindromeSubseq(const std::string& s) {
        return lps(s, 0, s.size() - 1);
    }
private:
    int lps(const std::string& s, int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (s[i] == s[j])
            return (i + 1 == j) ? 2 : 2 + lps(s, i + 1, j - 1);
        return std::max(lps(s, i + 1, j), lps(s, i, j - 1));
    }
};

Go

func longestPalindromeSubseq(s string) int {
    var lps func(i, j int) int
    lps = func(i, j int) int {
        if i > j {
            return 0
        }
        if i == j {
            return 1
        }
        if s[i] == s[j] {
            if i+1 == j {
                return 2
            }
            return 2 + lps(i+1, j-1)
        }
        a := lps(i+1, j)
        b := lps(i, j-1)
        if a > b {
            return a
        }
        return b
    }
    return lps(0, len(s)-1)
}

Java

class Solution {
    public int longestPalindromeSubseq(String s) {
        return lps(s, 0, s.length() - 1);
    }
    private int lps(String s, int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (s.charAt(i) == s.charAt(j))
            return (i + 1 == j) ? 2 : 2 + lps(s, i + 1, j - 1);
        return Math.max(lps(s, i + 1, j), lps(s, i, j - 1));
    }
}

Kotlin

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        fun lps(i: Int, j: Int): Int {
            if (i > j) return 0
            if (i == j) return 1
            if (s[i] == s[j])
                return if (i + 1 == j) 2 else 2 + lps(i + 1, j - 1)
            return maxOf(lps(i + 1, j), lps(i, j - 1))
        }
        return lps(0, s.length - 1)
    }
}

Python

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        def lps(i: int, j: int) -> int:
            if i > j:
                return 0
            if i == j:
                return 1
            if s[i] == s[j]:
                if i + 1 == j:
                    return 2
                return 2 + lps(i + 1, j - 1)
            return max(lps(i + 1, j), lps(i, j - 1))
        return lps(0, len(s) - 1)

Rust

impl Solution {
    pub fn longest_palindrome_subseq(s: &str) -> usize {
        fn lps(s: &[u8], i: usize, j: usize) -> usize {
            if i > j { return 0; }
            if i == j { return 1; }
            if s[i] == s[j] {
                if i + 1 == j { 2 } else { 2 + lps(s, i + 1, j - 1) }
            } else {
                let a = lps(s, i + 1, j);
                let b = lps(s, i, j - 1);
                a.max(b)
            }
        }
        let bytes = s.as_bytes();
        lps(bytes, 0, bytes.len().saturating_sub(1))
    }
}

TypeScript

class Solution {
    longestPalindromeSubseq(s: string): number {
        function lps(i: number, j: number): number {
            if (i > j) return 0;
            if (i === j) return 1;
            if (s[i] === s[j])
                return (i + 1 === j) ? 2 : 2 + lps(i + 1, j - 1);
            return Math.max(lps(i + 1, j), lps(i, j - 1));
        }
        return lps(0, s.length - 1);
    }
}

Complexity

• ⏰ Time complexity: O(2^N), since each call can branch into two subproblems and the recursion tree grows exponentially.
• 🧺 Space complexity: O(N) for the recursion stack (maximum depth is the string length).

Method 3 – Top Down DP (Memoization)

Intuition

The plain recursive approach recalculates the same subproblems many times. For e.g. In the below tree, L(1,4) is computed twice, showing the repetitive work that memoization can avoid.

graph TD
    L05("L(0,5)")
    L15("L(1,5)")
    L04("L(0,4)")
    L25("L(2,5)")
    L14a("L(1,4)")
    L14b("L(1,4)")
    L03("L(0,3)")
    L05 --> L15
    L05 --> L04
    L15 --> L25
    L15 --> L14a
    L04 --> L14b
    L04 --> L03
    %% Highlight repeated subproblem
    style L14a fill:#f9f,stroke:#333,stroke-width:2px
    style L14b fill:#f9f,stroke:#333,stroke-width:2px

By storing results for each substring (i, j) in a table (memoization), we avoid redundant work and reduce the time complexity to polynomial.

Approach

1. Use a 2D array or map to cache results for each (i, j) pair.
2. On each recursive call, check if the result is already computed; if so, return it.
3. Otherwise, compute as in the recursive approach, store the result, and return it.

Code

C++

#include <vector>
class Solution {
public:
    int longestPalindromeSubseq(const std::string& s) {
        int n = s.size();
        std::vector<std::vector<int>> memo(n, std::vector<int>(n, -1));
        return lps(s, 0, n - 1, memo);
    }
private:
    int lps(const std::string& s, int i, int j, std::vector<std::vector<int>>& memo) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (memo[i][j] != -1) return memo[i][j];
        if (s[i] == s[j])
            memo[i][j] = (i + 1 == j) ? 2 : 2 + lps(s, i + 1, j - 1, memo);
        else
            memo[i][j] = std::max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo));
        return memo[i][j];
    }
};

Go

func longestPalindromeSubseq(s string) int {
    n := len(s)
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, n)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    var lps func(i, j int) int
    lps = func(i, j int) int {
        if i > j {
            return 0
        }
        if i == j {
            return 1
        }
        if memo[i][j] != -1 {
            return memo[i][j]
        }
        if s[i] == s[j] {
            if i+1 == j {
                memo[i][j] = 2
            } else {
                memo[i][j] = 2 + lps(i+1, j-1)
            }
        } else {
            a := lps(i+1, j)
            b := lps(i, j-1)
            if a > b {
                memo[i][j] = a
            } else {
                memo[i][j] = b
            }
        }
        return memo[i][j]
    }
    return lps(0, n-1)
}

Java

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] memo = new int[n][n];
        for (int[] row : memo) java.util.Arrays.fill(row, -1);
        return lps(s, 0, n - 1, memo);
    }
    private int lps(String s, int i, int j, int[][] memo) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (memo[i][j] != -1) return memo[i][j];
        if (s.charAt(i) == s.charAt(j))
            memo[i][j] = (i + 1 == j) ? 2 : 2 + lps(s, i + 1, j - 1, memo);
        else
            memo[i][j] = Math.max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo));
        return memo[i][j];
    }
}

Kotlin

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val n = s.length
        val memo = Array(n) { IntArray(n) { -1 } }
        fun lps(i: Int, j: Int): Int {
            if (i > j) return 0
            if (i == j) return 1
            if (memo[i][j] != -1) return memo[i][j]
            memo[i][j] = if (s[i] == s[j]) {
                if (i + 1 == j) 2 else 2 + lps(i + 1, j - 1)
            } else {
                maxOf(lps(i + 1, j), lps(i, j - 1))
            }
            return memo[i][j]
        }
        return lps(0, n - 1)
    }
}

Python

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        memo = [[-1] * n for _ in range(n)]
        def lps(i: int, j: int) -> int:
            if i > j:
                return 0
            if i == j:
                return 1
            if memo[i][j] != -1:
                return memo[i][j]
            if s[i] == s[j]:
                if i + 1 == j:
                    memo[i][j] = 2
                else:
                    memo[i][j] = 2 + lps(i + 1, j - 1)
            else:
                memo[i][j] = max(lps(i + 1, j), lps(i, j - 1))
            return memo[i][j]
        return lps(0, n - 1)

Rust

impl Solution {
    pub fn longest_palindrome_subseq(s: &str) -> usize {
        let n = s.len();
        let mut memo = vec![vec![-1; n]; n];
        let bytes = s.as_bytes();
        fn lps(s: &[u8], i: usize, j: usize, memo: &mut Vec<Vec<i32>>) -> i32 {
            if i > j { return 0; }
            if i == j { return 1; }
            if memo[i][j] != -1 { return memo[i][j]; }
            memo[i][j] = if s[i] == s[j] {
                if i + 1 == j { 2 } else { 2 + lps(s, i + 1, j - 1, memo) }
            } else {
                lps(s, i + 1, j, memo).max(lps(s, i, j - 1, memo))
            };
            memo[i][j]
        }
        lps(bytes, 0, n.saturating_sub(1), &mut memo) as usize
    }
}

TypeScript

class Solution {
    longestPalindromeSubseq(s: string): number {
        const n = s.length;
        const memo: number[][] = Array.from({ length: n }, () => Array(n).fill(-1));
        function lps(i: number, j: number): number {
            if (i > j) return 0;
            if (i === j) return 1;
            if (memo[i][j] !== -1) return memo[i][j];
            if (s[i] === s[j]) {
                if (i + 1 === j) memo[i][j] = 2;
                else memo[i][j] = 2 + lps(i + 1, j - 1);
            } else {
                memo[i][j] = Math.max(lps(i + 1, j), lps(i, j - 1));
            }
            return memo[i][j];
        }
        return lps(0, n - 1);
    }
}

Complexity

• ⏰ Time complexity: O(N^2), since there are O(N^2) unique subproblems and each is solved once.
• 🧺 Space complexity: O(N^2), for the memoization table.

Method 4 – Bottom-up DP (Tabulation)

Intuition

We can build the solution for the longest palindromic subsequence by solving all smaller substrings first and combining their results. For example, for the string "ACECCBA", we first fill in all single characters (which are palindromes of length 1), then two-character substrings, and so on, until we solve for the whole string.

Approach

1. Create a 2D table dp where dp[i][j] stores the length of the longest palindromic subsequence in s[i..j].
2. Initialize all dp[i][i] = 1 (single characters).
3. For substrings of length 2 to N, fill the table:
   • If s[i] == s[j], then dp[i][j] = 2 + dp[i+1][j-1].
   • Else, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
4. The answer is dp[0][n-1].

Code

C++

class Solution {
public:
    int longestPalindromeSubseq(const std::string& s) {
        int n = s.size();
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
        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[i] == s[j])
                    dp[i][j] = (len == 2) ? 2 : 2 + dp[i+1][j-1];
                else
                    dp[i][j] = std::max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
};

Go

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }
    for l := 2; l <= n; l++ {
        for i := 0; i <= n-l; i++ {
            j := i + l - 1
            if s[i] == s[j] {
                if l == 2 {
                    dp[i][j] = 2
                } else {
                    dp[i][j] = 2 + dp[i+1][j-1]
                }
            } else {
                if dp[i+1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i+1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[0][n-1]
}

Java

class Solution {
    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] = (len == 2) ? 2 : 2 + dp[i+1][j-1];
                else
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
}

Kotlin

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val n = s.length
        val dp = Array(n) { IntArray(n) }
        for (i in 0 until n) dp[i][i] = 1
        for (len in 2..n) {
            for (i in 0..n-len) {
                val j = i + len - 1
                dp[i][j] = if (s[i] == s[j]) {
                    if (len == 2) 2 else 2 + dp[i+1][j-1]
                } else {
                    maxOf(dp[i+1][j], dp[i][j-1])
                }
            }
        }
        return dp[0][n-1]
    }
}

Python

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for l in range(2, n+1):
            for i in range(n-l+1):
                j = i + l - 1
                if s[i] == s[j]:
                    dp[i][j] = 2 if l == 2 else 2 + dp[i+1][j-1]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]

Rust

impl Solution {
    pub fn longest_palindrome_subseq(s: &str) -> usize {
        let n = s.len();
        let bytes = s.as_bytes();
        let mut dp = vec![vec![0; n]; n];
        for i in 0..n { dp[i][i] = 1; }
        for len in 2..=n {
            for i in 0..=n-len {
                let j = i + len - 1;
                dp[i][j] = if bytes[i] == bytes[j] {
                    if len == 2 { 2 } else { 2 + dp[i+1][j-1] }
                } else {
                    dp[i+1][j].max(dp[i][j-1])
                };
            }
        }
        dp[0][n-1]
    }
}

TypeScript

class Solution {
    longestPalindromeSubseq(s: string): number {
        const n = s.length;
        const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
        for (let i = 0; i < n; ++i) dp[i][i] = 1;
        for (let len = 2; len <= n; ++len) {
            for (let i = 0; i <= n - len; ++i) {
                const j = i + len - 1;
                if (s[i] === s[j])
                    dp[i][j] = (len === 2) ? 2 : 2 + dp[i+1][j-1];
                else
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
}

Complexity

• ⏰ Time complexity: O(N^2), since we fill an N x N table.
• 🧺 Space complexity: O(N^2), for the DP table.

Dry Run

Let's dry run the bottom-up DP for s = "bbbab":

1. Initialize dp[i][i] = 1 for all i (single characters).
2. For substrings of length 2: dp[1][2] = 2 for the substring "bb".
3. For length 3: dp[0][2] = 3 for "bbb".
4. For length 4: dp[0][3] = 3 for "bbba".
5. For length 5: dp[0][4] = 4 for "bbbab" (since s[0] == s[4], add 2 to dp[1][3]).
6. The final answer is dp[0][4] = 4.