Minimum Insertions to Achieve k-Palindrome

You are given a string s and an integer k. A string is called a k-palindrome if it can be transformed into a palindrome by removing at most k characters.

Your task is to determine the minimum number of characters that need to be inserted into s so that it becomes a k-palindrome. In other words, if the string can already be transformed into a palindrome by removing up to k characters, then no insertion is needed and you should output 0. Otherwise, output the number of extra insertions required after utilizing the allowed removals.

The solution involves finding the longest palindromic subsequence (LPS) of s. Let n be the length of s and LPS be the length of the longest palindromic subsequence. The minimum number of insertions needed to make the entire string a palindrome is given by:

\( \text{min_insertions} = n - LPS \)

If \( \text{min_insertions} \leq k \), then removal operations are sufficient and no insertion is required. Otherwise, the result is \( \text{min_insertions} - k \).

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains a non-empty string s composed of lowercase English letters.
2. The second line contains an integer k representing the maximum number of characters allowed to be removed.

outputFormat

Output a single integer to stdout, representing the minimum number of insertions required to make s a k-palindrome.

abacd
1

1