Min insertions for a palindrome

Challenge

Implement:

int min_insertions_palindrome(const char *s);

Return the minimum number of characters to insert anywhere so that s becomes a palindrome.

Input format

A string.

Output format

Minimum insertions.

Constraints

Answer is len - LPS(s).

Starter code

#include <stddef.h>
/* Minimum characters to insert anywhere to make s a palindrome. */
int min_insertions_palindrome(const char *s){ (void)s; return -1; }

Common mistakes

Trying to reason about insertions directly instead of via the palindromic subsequence.

Edge cases to handle

A palindrome needs 0; empty/single needs 0.

Background lessons

• Palindrome DP