Connection Status:
Competition Arena > GooseTattarrattatDiv1

GooseTattarrattatDiv1

SRM 589 · 2013-06-25 · by snuke

SRM 589 · 2013-06-25 · by snuke · Graph Theory, Greedy
Class Name: GooseTattarrattatDiv1
Return Type: int
Method Name: getmin
Arg Types: (string)
Problem Statement

Problem Statement

Goose Tattarrattat has a String S of lowercase letters. Tattarrattat wants to change her string into a palindrome: a string that reads the same forwards and backwards. (For example, "racecar" is a palindrome.)


She will do this in a series of steps. In each step, Tattarrattat will choose two letters of the alphabet: X and Y. She will then change each X in her string into a Y. Changing each single character takes 1 second.


For example, if S="goose" and Tattarrattat chooses X='o' and Y='e' in the next step, the step will take 2 seconds (because there are two 'o's in S) and after the step she would have S="geese".


You are given the String S. Return the smallest number of seconds in which Tattarrattat can change S into a palindrome.

Notes

  • Tattarrattat must always change all occurrences of the chosen letter into the other one; she is not allowed to change only some of the occurrences.

Constraints

  • S will contain between 1 and 50 characters, inclusive.
  • Each character in S will be a lowercase letter ('a'-'z').
Examples
0)
"geese"
Returns: 2

There are many ways how Tattarrattat can change this S into a palindrome. For example, she could do it in two steps as follows: Change all 'g's to 'e's: this takes 1 second and produces the string "eeese". Change all 'e's to 's's: this takes 4 seconds and produces the string "sssss". This way took her 1+4 = 5 seconds. However, there are faster ways. The best one only takes 2 seconds. For example, she can first change all 'g's to 'e's (1 second), and then change all 's's to 'e's (1 second), obtaining the palindrome "eeeee".

1)
"tattarrattat"
Returns: 0

This string is already a palindrome so no changes are needed.

2)
"xyyzzzxxx"
Returns: 2
3)
"dogeeseseegod"
Returns: 0
4)
"palindrome"
Returns: 5

Submissions are judged against all 189 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GooseTattarrattatDiv1 with a public method int getmin(string S) · 189 test cases · 2 s / 256 MB per case

Submitting as anonymous