NearPalindromesDiv2
SRM 791 · 2020-10-16 · by laoriu
Problem Statement
A string is called an even palindrome if its length is even and it reads the same forwards and backwards. E.g., "noon", "aaaaaa" and "repaiddiaper" are even palindromes but "eerrdd" and "tacocat" aren't. (This is because "eerrdd" is not a palindrome and "tacocat" has an odd number of letters.)
A string is called a even near-palindrome if we can rearrange its characters to make it an even palindrome. For example, "aaaaaa", "nono" and "eerrdd" are even near-palindromes but "aaa" and "abcd" aren't. (You can rearrange "eerrdd" to form the even palindrome "redder".)
Suppose X and Y are two different strings of the same length. Let i be the smallest index such that the characters X[i] and Y[i] differ. If X[i] < Y[i], we say that X is lexicographically smaller than Y, and vice versa. For example, "ramp" < "rats" because 'm' < 't'.
You are given a
You are allowed to perform a sequence of operations. In each operation you can choose an index into S and replace that character by any other lowercase English letter. (You are not allowed to add or remove characters.)
Your primary goal is to turn S into an even near-palindrome T using as few operations as possible. Your secondary goal is to find the lexicographically smallest among all such T. Find and return that T.
Constraints
- S will have between 2 and 2,500 characters, inclusive.
- The length of S will be even.
- Each character in S will be a lowercase English letter ('a'-'z').
"eerdrd" Returns: "eerdrd"
This is already an even near-palindrome, so no operations are needed. The only string T that can be produced in zero operations is the original string.
"abcdhgfe" Returns: "aacceffe"
We need four operations to turn this S into an even near-palindrome. There are many other ways to do it in four operations. For example, we could produce the string "aacchhff", the string "abcdabcd", or the string "abcddcba". The returned string "aacceffe" is the lexicographically smallest among all these strings.
"topcoder" Returns: "codcodee"
Here the minimum number of operations needed is three. The string "codcodee" is an even near-palindrome because it can be rearranged into the even palindrome "codeedoc".
"aaabbbaa" Returns: "aaaabbaa"
We need just a single operation: changing any 'a' into 'b' or any 'b' into 'a' will change this string into an even near-palindrome. The lexicographically smallest T is produced by changing the first 'b' into an 'a'.
"aa" Returns: "aa"
Submissions are judged against all 140 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NearPalindromesDiv2 with a public method string solve(string S) · 140 test cases · 2 s / 256 MB per case