UVa 10716 - Evil Straw Warts Live

// UVa 10716 - Evil Straw Warts Live
// Greedy

#include <iostream>
#include <string>
#include <map>
using namespace std;

bool is_palindromic(string s) {
	map<char, int> count;
	for (int i = 0; i < s.length(); i++)
		count[s[i]]++;
	int odds = 0;
	for (int i = 0; i < s.length(); i++)
		if (count[s[i]] & 1) {
			odds++;
			count[s[i]] = 0;
		}
	return odds <= 1;
}

int move(int from, int to, string& s) {
	int inc = (from < to ? 1 : -1);
	char tmp = s[from];
	for (int k = from; k != to; k += inc)
		s[k] = s[k + inc];
	s[to] = tmp;
	return (to - from) * inc;
}

int main() {
	int t;
	for (cin >> t; t; t--) {
		string s;
		cin >> s;
		if (!is_palindromic(s))
			cout << "Impossible" << endl;
		else {
			int sol = 0;
			int a = 0, b = s.length() - 1;
			while (a < b) {
				if (s[a] != s[b]) {
					map<char, int> right_most;
					for (int k = b; k >= a; k--) {
						if (right_most[s[k]] == 0)
							right_most[s[k]] = k;
					}
					int best = a;
					for (int k = a + 1; k <= b; k++) {
						if (k - a + b - right_most[s[k]] < best - a + b - right_most[s[best]])
							best = k;
					}
					sol += move(right_most[s[best]], b, s);
					sol += move(best, a, s);
				}
				a++;
				b--;
			}
			cout << sol << endl;
		}
	}

	return 0;
}