PasswordXPalindrome
TCO12 Round 1C · 2012-03-27 · by fushar
TCO12 Round 1C · 2012-03-27 · by fushar · Graph Theory
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:
You are given aString 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.
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:
- Choose two different integers A and B such that 0 <= A < B < X.
- Swap the characters at (0-based) positions A and B of the current password.
You are given a
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.
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