Connection Status:
Competition Arena > PasswordXPalindrome

PasswordXPalindrome

TCO12 Round 1C · 2012-03-27 · by fushar

TCO12 Round 1C · 2012-03-27 · by fushar · Graph Theory
Class Name: PasswordXPalindrome
Return Type: int
Method Name: minSwaps
Arg Types: (string)
Problem Statement

Problem Statement

Ms. Ciel loves rabbits. She has a large special cage for her rabbits. The special cage is protected by a secret password consisting of exactly X characters. Each character of her password is one of 'a'-'z'. Due to the security policy of the cage, each of the letters 'a'-'z' only occurs at most twice in the password.

Bored with her current password, Ms. Ciel wants to change her password into a palindrome. (A string is called palindrome if it reads the same forwards and backwards.) To change the password, Ms. Ciel may perform this operation (that consists of two steps) zero or more times:

  1. Choose two different integers A and B such that 0 &lt= A < B < X.
  2. Swap the characters at (0-based) positions A and B of the current password.

You are given a String password consisting of X characters which represents Ms. Ciel's initial password. Return the minimum number of operations Ms. Ciel needs to change password into a palindrome. If this is not possible, return -1 instead.

Constraints

  • password will contain between 1 and 50 characters, inclusive.
  • Each character of password will be one of 'a'-'z'.
  • Each of the letters 'a'-'z' will occur at most twice in password.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
"levle"
Returns: 1

One possible solution is to swap the last two characters to change the password into "level".

1)
"racecar"
Returns: 0

The password is already a palindrome.

2)
"abcdadcb"
Returns: 3

One possible solution: Swap the characters at positions 4 and 7. The password becomes "abcdbdca". Swap the characters at positions 5 and 6. The password becomes "abcdbcda". Swap the characters at positions 4 and 6. The password becomes "abcddcba".

3)
"msmscielciel"
Returns: 5
4)
"hicanyouguesstodaywriter"
Returns: -1

It is not possible to change this password into a palindrome.

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

Coding Area

Language: C++17 · define a public class PasswordXPalindrome with a public method int minSwaps(string password) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous