NearPalindromesDiv1
SRM 791 · 2020-10-16 · by laoriu
Problem Statement
A string is called a palindrome if it reads the same forwards and backwards. E.g., "a", "noon" and "tacocat" are palindromes but "cocoa" isn't.
A string is called a near-palindrome if we can rearrange its characters to make it a palindrome. For example, "aaa", "cocoa" and "xxyyzz" are near-palindromes but "abc" isn't.
You are given a
Determine and return the smallest number of operations needed to turn S into a near-palindrome.
Constraints
- S will contain between 1 and 2,500 characters, inclusive.
- Each character of S will be a lowercase English letter ('a'-'z').
"cocoa" Returns: 0
This is already a near-palindrome, no operations are needed.
"daddy" Returns: 2
One optimal solution is to increment S[4] twice, changing the input string into the near-palindrome "dadda". (The string "dadda" is a near-palindrome because we can rearrange its letters to get a palindrome. One of the palindromes we can obtain this way is "dadad".)
"abcdefgh" Returns: 4
"topcoder" Returns: 12
"aaaaabbaabaabbababbababababaaaaabaababababaababbbaaabbababbabbbbabbaaabaabaaababababbbbabaababaaaabbabbbabbbbabbabaaaabaabbabbaaababbbabaabbbbabbaabaaaaaaaabaaaaabaaaabaabbaabbabaaabaaabbbabbabaaaababbaaabbbabbaaaabbaaababaabbabaabaabbaababaababababbaabbaaabababaaabbbaaaabbabbbbaabbaaaaaababaabbabbaabbabbaaaabaabbbbbbabbbabbbaaabababbaaaaaaababbbaaabaaabbbbbaabaabbabababbabbbababababbabbbabaaaaababaabbbbbaaabaababbbbaabababbabbbbbababbabbaaaaaabaaabaabbaabbbabbbbabaabaabaaaaaababaababbaaabbaabbaaaaaabbabbaabbbabbaabbaaaabbbabaaabbbaabaabbbbaaaabbbbaaabababbbabaabbbbabbaabbbbaabaabbbaababbabbbbabbbabbabbbabaabbbbabbabaaaabbbbabaababbabaaabababbbbabbbbabaabbbabaaaabbaababbaabaabaaaabbbaabbaaaabbbbbbaaaabbbbbbaabbbbaababababaaabbbbabbaababbbaabbbabbbbabbbaaababbbabbbaababbbbbaababaabaababbbababbabaabbababbbabbbaaabbbbbaaabbabaabbababbabbbbbaabbaaabbabbbaababbababaabbabbaabababababbbbababaaabbbaabbbabbbabbabbabbaaabbbbabbbabbabaabaabaaabbbaababbbbbaaaabbbbaabbbbbababaaaabaaabbabbbbaabaaaaaabaabababbbbbaabaabbbbbbaaaababbabaabbabbaababbbaaaababbbbbaabaabbbaabbabaaabbabaaaabaaaabbaabbabaabbbbaabbbbbabaaabbaabbbabbbabaaabbbbabbabbaababaaabbbbbbaaabababaaaaaabbabaababbbaaaabaabbbabbababbabbbbabbaabbbababaaabbbbaabbaabbabbbbbabbaabaabbbbaabbabbbabbabbaaabbbaaaaaabababbabbbbbbbaaabaaabbabaaabbaabbbbababbbbbbaaabbaaababbbbbbbbabaabbabbbbbaabbbbbbbbbababaaaabbaaaaabbbbabbababbaababbbbaaaaabbbbababbbabbbabaaaaabaaaaaaababaabbbbbaabaabaaaababaaaaababbbaabaabbabbabbbabbbbaaabbabbbabbaaaababbaaabaababbbabbaaababaaabaaabbbbaabbabaabbbabbbbaababaababaaaabaabbabaaabaaababbbbababaaaabbbaaaabbabbaaababaababababbbaabbabbabaabbbbbbbaabaabbababbaabababaababbaaabaabaabbbbaabbbbbaabbbbaaabbabaaabbaabbabbaabbaaabababaabbbabababbaabbbbbbbbbabaabbabbaabbbabaaaabbbaaabbbbaabbbbbabbbaaabbaabbabbbbaaabbbbbbaabbaabbbbbabbabbaabaaababaaaabbbbabababbaaabababbababaaaabaaabbbbabbbbbbbaaaabbbaaabbaaaaabaabaabaaaababbbaaaabaaabbbaababaaaabbbaabbaabbabbbabaaabaabaaabbbbbbbaaabbabababbababaaaabbbbaaaabbbaababbababbbbbababaaaaabbbaaabbabaabbbaaaabbbaababbabbaababaaaabbbaaaaaabaabbaaababaabbabbbabaaaaaabbbaabbaabaabbbbabbabbaabaaaabbaababbbbbbbaabbaaababbbaabbabbbabaaaabbbaabbbababbababbabaabaaababbabbbbabbbabbabbbbbabaabbaaabbbbaaabbaaababbbaababbababbbabbbbbaaababbabababababaabaaaaaabbaaabbbbabbaababbbbababbbbbababbbbbbbaababbaaababbaabbababaaababbabbabaabbbbbbbbabababaaabbaaabbbbbaabbbbabbbbbbaaaabababbbabbabbaaabbbaabaababbabaabaaaaaaabaaaaabaabbbaabbbbabbabbaaaaaabaabababaabbaabaaaaabababaaa" Returns: 0
Submissions are judged against all 160 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NearPalindromesDiv1 with a public method int solve(string S) · 160 test cases · 2 s / 256 MB per case