GooseTattarrattatDiv2
SRM 589 · 2013-06-25 · by snuke
Problem Statement
Goose Tattarrattat has a
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 an 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
Constraints
- S will contain between 1 and 50 characters, inclusive.
- Each character in S will be a lowercase letter ('a'-'z').
"geese" Returns: 2
There are many ways how Tattarrattat can change this S into a smooth string. 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 smooth string "eeeee".
"tattarrattat" Returns: 6
"www" Returns: 0
This string is already smooth so no changes are needed.
"topcoder" Returns: 6
"abcdefghijklmnopqrstuvwxyz" Returns: 25
Submissions are judged against all 85 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GooseTattarrattatDiv2 with a public method int getmin(string S) · 85 test cases · 2 s / 256 MB per case