程序计算在Python中使其回文所需的最小交换次数
假设我们有一个字符串s，我们必须找到使其成为回文式所需的最小相邻交换数。如果没有这种解决方法，则返回-1。
因此，如果输入类似于s=“xxyy”，则输出将为2，因为我们可以交换中间的“x”和“y”，使字符串为“xyxy”，然后交换前两个“x”和“ y”得到“yxxy”，这就是回文。
Example(Python)
让我们看下面的实现以更好地理解-
class Solution:
def solve(self, s):
def util(s):
seen = {}
for i in s:
seen[i] = seen.get(i, 0) + 1
odd_count = 0
for k, val in seen.items():
if val & 1 == 1:
odd_count += 1
if odd_count == 2:
return False
return True
swaps = 0
if util(s):
left = 0
right = len(s) - 1
s = list(s)
while left < right:
if s[left] != s[right]:
k = right
while k > left and s[k] != s[left]:
k -= 1
if k == left:
swaps += 1
s[left], s[left + 1] = s[left + 1], s[left]
else:
while k < right:
s[k], s[k + 1] = s[k + 1], s[k]
k += 1
swaps += 1
left += 1
right -= 1
else:
left += 1
right -= 1
return swaps
return -1
ob = Solution()
s = "xxyy"
print(ob.solve(s))输入值
"xxyy"
输出结果
2