Minimum Insertions to Make a String Palindrome

DiffPush Tier Dynamic Programming · DP on Strings O(n^2) · O(n^2)

The Palindrome Patch Ledger

A legacy router stores configuration keys that must read as palindromes for its checksum logic to accept them. Upgrades may only prepend or append characters — one insertion per step. The migration tool computes the fewest insertions that turn each legacy key into a valid palindrome before the firmware swap.

Input: A string s.

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

Constraints

1 <= len(s) <= 500
s consists of lowercase English letters

Examples

Example 1

Input: {"s":"zzazz"}
Output: 0
The key is already a palindrome.

Example 2

Input: {"s":"mbadm"}
Output: 2
"mbdadbm" or "mdbabdm" both need two insertions.

Solve this in your browser →

Also on LeetCode ↗