GooseTattarrattatDiv1 | Topcoder Archive

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.

Definition

Class:: GooseTattarrattatDiv1
Method:: getmin
Parameters:: String
Returns:: int
Method signature:: int getmin(String S)
(be sure your method is public)

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

```
"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".
```
"tattarrattat"
```
```
Returns: 0
```
This string is already a palindrome so no changes are needed.
```
"xyyzzzxxx"
```
```
Returns: 2
```

"xrepayuyubctwtykrauccnquqfuqvccuaakylwlcjuyhyammag"

Returns: 11

```
"abaabb"
```
```
Returns: 3
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.