Construct the Longest Palindrome

You are given an integer k and a string s consisting of lowercase letters only. Your task is to remove characters from s (without reordering the remaining characters) in order to obtain a palindromic string. However, you are allowed to remove at most k characters during this process.

Your goal is to output the longest palindromic string that can be created under these rules. If there are several possible answers, any one of them is acceptable. Note that even if the minimum number of deletions required to make the string fully palindromic exceeds k, you should still form the longest palindrome possible by judiciously choosing deletions.

Examples:

• For k = 2 and s = "abcbda", one possible answer is abcba.
• For k = 1 and s = "abcde", one possible answer is a.
• For k = 3 and s = "banana", one possible answer is anana.

inputFormat

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

1. The first line contains a single integer k which is the maximum number of characters you are allowed to remove.
2. The second line contains the string s consisting of only lowercase letters.

outputFormat

Print to standard output (stdout) the longest palindromic string that can be formed from s by removing at most k characters.

2
abcbda

abcba