P12592题解

洛谷同文链接

P12592 重生有惊喜 题解

题意

给定一个字符串，你可以任意次交换任意两个字符，问能否通过这些操作让字符串变成回文串。

思路

因为可以任意次交换字符，这就意味着我们可以重新排列字符顺序。

要判断是否能构成回文串，只需要判断字符出现的频次是否满足回文的结构要求。

回文的字符判断方法

• 若字符串长度是偶数：所有字符必须出现偶数次。
• 若字符串长度是奇数：最多只有一个字符可以出现奇数次，其余字符必须出现偶数次。

代码

我们只需统计每个字符出现的次数，判断有多少个字符出现了奇数次即可。

from collections import Counter

T = int(input())
for _ in range(T):
    s = input()
    a = Counter(s)
    b = sum(1 for c in a.values() if c % 2 == 1)
    if b <= 1:
        print("Yes")
    else:
        print("No")