Longest palindromic subsequence

Challenge

Implement:

int lps(const char *s);

Return the length of the Longest Palindromic Subsequence of s.

Input format

A string.

Output format

LPS length.

Constraints

Interval DP over substrings (i..j).

Starter code

#include <stddef.h>
/* Length of the Longest Palindromic Subsequence of s. */
int lps(const char *s){ (void)s; return 0; }

Common mistakes

Iterating in the wrong order — inner substrings must be solved before outer ones.

Edge cases to handle

Single char -> 1; empty -> 0.

Background lessons

• Palindrome DP