OrthogonalAnagram

TCO11 Semifinal 1 · 2011-05-07 · by misof

TCO11 Semifinal 1 · 2011-05-07 · by misof · Greedy, String Manipulation

Show categories

Class Name: OrthogonalAnagram

Return Type: String

Method Name: solve

Arg Types: (string)

Problem Statement

An anagram of a string is a string containing precisely the same letters, possibly in different order. For example, "porter", "report", and "eoprrt" are all anagrams of the string "porter" (and of each other). The string "potter" is not their anagram, as the numbers of "t"s and "r"s differ.

Strings S and T are orthogonal if they are of the same length and differ in each position. For instance, the strings "card" and "dear" are orthogonal. The strings "perk" and "card" are not orthogonal, because their third letters are the same.

You are given a String S. Your method should return the lexicographically smallest anagram of S that is orthogonal to S. If no such string exists, return an empty String.

Notes

Given two distinct strings of equal length, the lexicographically smaller one is the one with a smaller character in the first position where they differ.

Constraints

S will contain between 1 and 50 characters, inclusive.
Each character of S will be a lowercase letter ('a'-'z').

Examples

"dcba"
Returns: "abcd"

"edcba"
Returns: "abdce"

The two lexicographically smallest anagrams are "abcde" and "abced". Neither of these is orthogonal to S: they all share the same third letter ("c").

"aaaaa"
Returns: ""

Here it is clearly impossible to create an orthogonal anagram.

"abba"
Returns: "baab"

"qwqeqrqtqyquqiqoqpqaqsqdqfqgqhqjqkqlqzqxqcqvqbqnqm"
Returns: "aqbqcqdqeqfqgqhqiqjqkqlqmqnqoqpqrqsqtquqvqwqxqyqzq"

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

Coding Area

Language: C++17 · define a public class OrthogonalAnagram with a public method string solve(string S) · 128 test cases · 2 s / 256 MB per case