Python3 程序最小化要更改的字符，使字符串的左旋转和右旋转相同
旋转意味着我们必须向前或向后移动每个字符。向前意味着向右旋转(或逆时针)，向后意味着向左旋转(或顺时针)。
在这个问题中，我们给出了一个大小为 n 的字符串。我们的任务是找到要更改的字符的最小数量，以检查是否有可能使字符串的左旋转和右旋转相同。
让我们看下面带有解释的示例，以便更好地理解问题。
输入 1
str = "wxyz"
输出 1
2
解释
字符串的左旋转是 xyzw
字符串的右旋转是 zwxy
因此，根据观察，将位置 0 处的字符 str[0] = w 更改为 y，将位置 3 处的字符 str[3] = z 更改为 x。字符串变为 yxyx。
因此，答案是 2，因为左旋转和右旋转字符串都变为 xyxy。
输入 2
str = "aka"
输出 2
1
解释
字符串的左旋转是 aak
字符串的右旋转是 kaa
因此，根据观察，将位置 1 str[1] = k 处的字符更改为 a。字符串变为 aaa。
因此，答案是 1，因为左旋转和右旋转字符串都变为 aaa。
方法
在看到上面给出的字符串的示例后，让我们继续讨论该方法。
这种方法的想法基于观察。观察结果有两点-
当我们有一个偶数长度的字符串时，则字符串中偶数索引和奇数索引中存在的所有字符必须相同，以使右旋转和左旋转的字符串相同。
当我们有一个奇数长度的字符串时，则字符串中存在的所有字符必须相同，以使右旋转和左旋转的字符串相同。
让我们看下面的代码以更好地理解上述方法。
示例
# 查找要从字符串中删除的最少字符的函数
def getMinimumChange(str, n):
# 用变量 minNum 中的 N 初始化答案
minChanges = n
# 如果字符串的长度为偶数
if (n % 2 == 0):
# 为偶数索引创建频率数组
freqEvenIdx = {}
# 为奇数索引创建频率数组
freqOddIdx = {}
# 遍历 for 循环将频率数组 freqEvenddIdx 和 freqOddIdx 初始化为 0
for ch in range(ord('a'), ord('z') + 1):
freqEvenIdx[chr(ch)] = 0
freqOddIdx[chr(ch)] = 0
# 奇数和偶数索引
for i in range(n):
if (i % 2 == 0):
if str[i] in freqEvenIdx:
freqEvenIdx[str[i]] += 1
else:
if str[i] in freqOddIdx:
freqOddIdx[str[i]] += 1
# 创建变量 evenIdxMax 和 OddIdxMax，分别存储偶数位字符和奇数位字符的最大频率
evenIdxMax = 0
oddIdxMax = 0
# 从 a 到 z 遍历 for 循环，更新变量 evenIdxMax 和 OddIdxMax
for ch in range(ord('a'), ord('z') + 1):
evenIdxMax = max(evenIdxMax, freqEvenIdx[chr(ch)])
oddIdxMax = max(oddIdxMax, freqOddIdx[chr(ch)])
# 更新 answerin 变量 minChanges
minChanges = minChanges - evenIdxMax - oddIdxMax
# 如果字符串的长度是奇数
else:
# 创建数组来存储字符串中字符的频率
freq = {}
# 初始化频率数组
for ch in range('a', 'z'):
freq[chr(ch)] = 0
# 遍历字符串时存储字符串中字符的频率
for i in range(n):
if str[i] in freq:
freq[str[i]] += 1
# 将字符串中字符的最大频率存储在变量 freqMax 中
freqMax = 0
# 遍历 for 循环以更新 freqMax
for ch in range('a', 'z'):
freqMax = max(freqMax, freq[chr(ch)])
# 更新变量 minChanges 中的答案
minChanges = minChanges - freqMax
# 返回最终答案 minChanges
return minChanges
str = "wxyz" # 给定字符串
n = len(str) # 获取给定字符串的大小
# 调用函数获取使左右旋转字符串相同的最小更改次数
res = getMinimumChange(str, n)
# 打印结果
print(
"使左右旋转字符串相同的最小更改次数为:"
)
print(res)
输出
使左右旋转字符串相同的最小更改次数为:2
时间和空间复杂度
上述代码的时间复杂度为 O(N)，因为我们遍历了 spring 和 number。
上述代码的空间复杂度为 O(1)，因为没有使用额外的空间来存储任何东西。
其中 N 是字符串的大小字符串。
结论
在本教程中，我们实现了一个 Python3 程序来最小化要更改的字符，以使字符串的左右旋转相同。我们实施了一种散列方法，因为我们必须存储频率。时间复杂度为 O(N)，空间复杂度为 O(1)，N 是给定字符串的大小。
