EqualizeStrings

TCO10 Round 1 · 2010-04-11 · by soul-net

TCO10 Round 1 · 2010-04-11 · by soul-net · Greedy

Show categories

Class Name: EqualizeStrings

Return Type: String

Method Name: getEq

Arg Types: (string, string)

Problem Statement

You have two Strings, s and t, and you want them to be equal. You can change individual letters in the Strings, but you cannot add or remove letters. In a single move, you can change any one letter in one String to the letter that comes directly before or after it in the alphabet. The alphabet wraps around, so you can also change 'a' to 'z' or 'z' to 'a'. You want to make the two Strings equal using the minimum possible number of moves. Return the resulting String. If there are multiple answers, return the one that comes earliest alphabetically.

Notes

A String comes earlier lexicographically than another one of the same length if and only if it has a character closer to the beginning of the alphabet in the first position at which they differ.

Constraints

s will contain between 1 and 50 characters, inclusive.
s and t will contain the same number of characters.
Each character of s and t will be a lowercase letter ('a'-'z').

Examples

"cat"
"dog"
Returns: "caa"

Use 1 move to change 'd' to 'c', 12 moves to change 'o' to 'a', 6 moves to change 'g' to 'a' and 7 moves to change 't' to 'a' for a total of 26 moves to get both Strings equal to "caa".

"abcdefghijklmnopqrstuvwxyz"
"bcdefghijklmnopqrstuvwxyza"
Returns: "abcdefghijklmnopqrstuvwxya"

Change every letter in t to its previous letter in the alphabet, using exactly one move per letter, with the exception of the last character; it's preferable to change the 'z' in s to 'a' to obtain a lexicographically earlier solution.

"programmingcompetitionsrule"
"programmingcompetitionsrule"
Returns: "programmingcompetitionsrule"

If both strings are equal, then you don't need any moves.

"topcoderopen"
"onlinerounds"
Returns: "onlcndaoondn"

"aazanamaobnbmbobpxxxyyyzzz"
"azanamaobnbmbobpbzyxzyxzyx"
Returns: "aaaaaaaaabbbbaaaaxxxyyxzyx"

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

Coding Area

Language: C++17 · define a public class EqualizeStrings with a public method string getEq(string s, string t) · 70 test cases · 2 s / 256 MB per case