#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; } |