LetterInterchange

TCCC07 Round 1A · 2007-07-30 · by andrewzta

TCCC07 Round 1A · 2007-07-30 · by andrewzta · Search, String Manipulation

Show categories

Class Name: LetterInterchange

Return Type: int[]

Method Name: interchangeWhich

Arg Types: (vector<string>, vector<string>)

Problem Statement

You are given a string of text. You must interchange two letters that are in different positions in the text to obtain a new string. Note that the two letters might be equal. For example, the string "aba" could become "baa", "aab", or "aba". You must choose the two letters such that the resulting string comes as early as possible alphabetically.

You will be given the text as two String[]s s1 and s2. Concatenate all elements of s1 and append the concatenation of all elements of s2 to obtain the text. Return a int[] containing exactly two elements: the 0-based indices of the letters to interchange. If there are multiple solutions, return the one with the smallest first index. If there's a tie, return the one among them with the smaller second index.

Constraints

s1 and s2 will each contain between 1 and 50 elements, inclusive.
Each element of s1 and each element of s2 will contain between 1 and 50 characters, inclusive.
Each element of s1 and each element of s2 will contain only lowercase letters ('a'-'z').

Examples

{"a", "b", "a"}
{"c", "a", "b", "a"}
Returns: {1, 6 }

The text is "abacaba". We interchange the 1-st and 6-th letters to obtain "aaacabb". This is the best possible new text.

{"aa"}
{"bb"}
Returns: {0, 1 }

The text here is "aabb". The best thing we can do here is interchange two equal letters. Anything else would result in a string that comes later alphabetically. To obtain the return value with smallest first element we interchange the 'a's.

{"a"}
{"b", "b"}
Returns: {1, 2 }

{"a"}
{"b", "c"}
Returns: {1, 2 }

{"ab"}
{"c", "a"}
Returns: {1, 3 }

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

Coding Area

Language: C++17 · define a public class LetterInterchange with a public method vector<int> interchangeWhich(vector<string> s1, vector<string> s2) · 142 test cases · 2 s / 256 MB per case