#include <iostream>
#include <string>
char other(char c)
{
if (c == 'a')
{
return 'b';
}
else
{
return 'a';
}
}
int min_moves(std::string str)
{
// Base case
if (str.size() == 1)
{
return 0;
}
else if (str.size() == 2)
{
if (str[0] == str[1])
{
return 0;
}
else
{
return -1;
}
}
int length = str.size();
if (str[0] == str[length - 1])
{
return min_moves(str.substr(1, length - 2));
}
else
{
int total = 0;
int left_ind = str.find(other(str[0]));
int right_ind = str.rfind(other(str[str.size() - 1]));
if (left_ind + 1 >= length - right_ind)
{
for (int i = right_ind; i < length - 1; ++i)
{
std::swap(str[i], str[i + 1]);
total += 1;
}
}
else
{
for (int i = 0; i < left_ind; ++i)
{
std::swap(str[i], str[i + 1]);
total += 1;
}
}
int partial = min_moves(str.substr(1, length - 2));
if (partial == -1)
{
return -1;
}
else
{
return partial + total;
}
}
}
int main()
{
std::string input;
std::cin >> input;
std::cout << min_moves(input) << "\n";
return EXIT_SUCCESS;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <iostream> #include <string> char other(char c) { if (c == 'a') { return 'b'; } else { return 'a'; } } int min_moves(std::string str) { // Base case if (str.size() == 1) { return 0; } else if (str.size() == 2) { if (str[0] == str[1]) { return 0; } else { return -1; } } int length = str.size(); if (str[0] == str[length - 1]) { return min_moves(str.substr(1, length - 2)); } else { int total = 0; int left_ind = str.find(other(str[0])); int right_ind = str.rfind(other(str[str.size() - 1])); if (left_ind + 1 >= length - right_ind) { for (int i = right_ind; i < length - 1; ++i) { std::swap(str[i], str[i + 1]); total += 1; } } else { for (int i = 0; i < left_ind; ++i) { std::swap(str[i], str[i + 1]); total += 1; } } int partial = min_moves(str.substr(1, length - 2)); if (partial == -1) { return -1; } else { return partial + total; } } } int main() { std::string input; std::cin >> input; std::cout << min_moves(input) << "\n"; return EXIT_SUCCESS; } |
English