Longest Palindromic Subsequence

Given a nonempty string s, return the length of its longest palindromic subsequence. A subsequence deletes zero or more characters without changing the order…

Given a nonempty string s, return the length of its longest palindromic subsequence. A subsequence deletes zero or more characters without changing the order of those kept; it need not be contiguous. A palindrome reads identically in both directions. Return only the length, not a reconstructed sequence. Characters are Unicode scalar values, not UTF-8 bytes, UTF-16 code units, or visual grapheme clusters. Do not normalize, case-fold, trim, or ignore characters. Combining marks are separate scalar values. Unpaired surrogates are outside the input domain.

- 1 <= number of Unicode scalar values in s <= 1000. - All Unicode scalar values are allowed; no unpaired surrogates. - The visualizer accepts 1..8 Unicode scalar values; longer valid inputs are coding-only.

Example 1: input s = "eeeme"; output 4. Keeping all four e characters gives "eeee"; the intervening m can be deleted.

Example 2: input s = "annb"; output 2. Keeping the adjacent n pair gives length 2; no longer palindrome exists.

Example 3: input s = "bbbab"; output 4. The four b characters form a subsequence even though the a interrupts the contiguous run.

Category: Strings. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.