Longest Palindromic Subsequence

Advanced

Longest Palindromic Subsequence Challenge!

Imagine you have a string, which could be a word or a sentence! πŸ§™β€β™‚οΈ Your magical task is to find the longest palindromic subsequence in this string. A subsequence doesn't need to be contiguous, but should maintain the order of characters.

For example, the word "character" has a longest palindromic subsequence "carac", because if we remove 'h', 't', and 'e', "carac" is a palindrome! Isn't that interesting?

Palindromes are words that read the same forward and backward, like "level" or "racecar".

Your mission is to write a magical function longest_palindromic_subsequence that takes a single string as its input and returns the longest palindromic subsequence as a string.

Examples:

longest_palindromic_subsequence("character") # Output: "carac" longest_palindromic_subsequence("agbdba") # Output: "abdba" # Output: "aca" or "ada" longest_palindromic_subsequence("banana") # Output: "anana"

Let’s see how long your palindrome can be! Give it a try! πŸš€

Geek
Inputs

Arg 1:

"character"
Expected Output
"carac"
Actual Output