Marquee Palindrome Inserts Problem

Marquee Palindrome Inserts Problem — ExecCode Hard DSA Practice

Solve the Marquee Palindrome Inserts problem on ExecCode. Free online hard DSA practice in String. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A marquee string must read the same forwards and backwards. You may insert letters anywhere (you may not delete). Interval DP asks, for every substring, the fewest inserts to make it a palindrome: if ends match, solve the inside; else insert one end and take the better side. Return the minimum number of insertions to make s a palindrome. You are given: s — the marquee text Return minimum insertions. Insertions can go anywhere, including the ends.

Examples

Input {'s': 'ab'}; Output 1. Input {'s': 'aa'}; Output 0. Input {'s': 'abc'}; Output 2

Constraints

Empty or length 1 needs 0 Any lowercase letters

Practice Marquee Palindrome Inserts free on ExecCode. Browse DSA problems, topic map, and placement guides.