Palindromic Algorithms

Problem Statement

Palindromic Algorithms A palindrome is a string that reads the same from either direction, for example ada . You are given a string s of lowercase English letters. You may perform the following two kinds of operations on it: Change a character: replace any single character of s by any lowercase English letter. Every replaced character counts as one change. Rearrange : reorder the characters of the string however you like. Rearranging is free and does not count as a change. Your task is to turn s into a palindrome of the same length using as few changes as possible . If several different palindromes can be reached with that same minimum number of changes, output the alphabetically smallest one. Input Format A single line containing the string s . Output Format Print a single line containing the alphabetically smallest palindrome that can be obtained from s with the minimum possible number of changes. Constraints 1 ≤ length of s ≤ 3 * 10^5 s consists of lowercase English letters ( a – z