本题没有可用的提交语言。

题目描述

回文串是指正读反读都相同的字符串。给定一个任意字符串（不一定是回文），计算通过相邻字符交换将其转换为回文串所需的最少交换次数。每次交换定义为反转两个相邻字符的顺序。

例如，字符串 "mamad" 可以通过以下$3$次交换变为回文串 "madam"：
$1$. 交换 "ad" → "mamda"
$2$. 交换 "md" → "madma"
$3$. 交换 "ma" → "madam"

输入格式

$-$第一行：测试用例数量$n$。
$-$接下来$n$行：每行一个长度不超过$8000$的小写字母字符串。

输出格式

$-$ 对于每个测试用例，输出最少交换次数；若无法转换为回文串，输出 "Impossible"。

样例输入 1

3
mamad
asflkj
aabb

样例输出 1

3
Impossible
2

来源

Waterloo local 2004.09.19

关键思路

$1$. 回文可行性检查：统计字符频率，若超过一个字符出现奇数次，则无法构成回文。
$2$. 贪心交换策略：
$-$ 从字符串两端向中间遍历，若两端字符不同，则在内侧找到匹配字符并通过相邻交换移至对应位置。
$-$ 每次交换的步数计入总次数。
$3$. 奇数长度处理：若字符串长度为奇数，允许中心字符不匹配，但需确保其余字符成对出现。

示例解析

$-$ "mamad"：
$-$ 步骤1：左'm'=右'd' → 交换'a'和'd'（"mamda"，$1$次）。
$-$ 步骤2：左'a'≠右'a' → 交换'm'和'd'（"madma"，$2$次）。
$-$步骤3：左'm'≠右'm' → 交换'a'和'm'（"madam"，$3$次）。
$-$ "asflkj"：字符频率不满足回文条件，直接输出 "Impossible"。
$-$ "aabb"：通过交换'b'和相邻字符（$2$次）得到 "abba"。