Python 将字符串的左旋转和右旋转相同的字符的最小更改数

旋转意味着我们必须将每个字符向前或向后移动。向前移动意味着右旋转（或逆时针），向后移动意味着左旋转（或顺时针）。

在这个问题中，我们给出了一个大小为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上将字符k更改为a。字符串变为aaa。

因此，答案是1，因为左旋转和右旋转的字符串都变为aaa。

方法

在看到上面给定字符串的示例后，让我们继续进行方法。

这种方法的思路是基于观察。观察有两点-

• 当字符串的长度为偶数时，在字符串的偶数索引和奇数索引处的所有字符必须相同，以使得左旋转和右旋转的字符串相同。

• 当字符串的长度为奇数时，字符串中的所有字符必须相同，以使得左旋转和右旋转的字符串相同。

让我们看下面的代码以更好地理解上述方法。

示例

# Function to find the minimum characters to be removed from the string
def getMinimumChange(str, n):
   # Initialize answer by N in variable minNum
   minChanges = n
   # If the length of the string is even
   if (n % 2 == 0):
      # Created frequency array for Even index
      freqEvenIdx = {}
      # Created frequency array for odd index
      freqOddIdx = {}
      # Traverse for loop to intialize both the frequency array freqEvenddIdx and freqOddIdx to 0
      for ch in range(ord('a'), ord('z') + 1):
         freqEvenIdx[chr(ch)] = 0
         freqOddIdx[chr(ch)] = 0
      # at odd and even index
      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
      # Create variable evenIdxMax and OddIdxMax to store maximum frequency of even place character and odd place character respectively
      evenIdxMax = 0
      oddIdxMax = 0
      # Traverse for loop from a to z to update variable evenIdxMax and OddIdxMax
      for ch in range(ord('a'), ord('z') + 1):
         evenIdxMax = max(evenIdxMax, freqEvenIdx[chr(ch)])
         oddIdxMax = max(oddIdxMax, freqOddIdx[chr(ch)])
      # Update the answerin variable minChanges
      minChanges = minChanges - evenIdxMax - oddIdxMax
   # If the length of the string is odd
   else:
      # Create array to store frequecy of character of the string
      freq = {}
      #  initialize the the freq array
      for ch in range('a', 'z'):
         freq[chr(ch)] = 0
      # Stores the frequency of the characters of the string while traversing the string
      for i in range(n):
         if str[i] in freq:
            freq[str[i]] += 1
      # Stores the maximum freuency of character of the string in variable freqMax
      freqMax = 0
      #  Traverse the for loop to update freqMax
      for ch in range('a', 'z'):
         freqMax = max(freqMax, freq[chr(ch)])
      # Update the answer in variable minChanges
      minChanges = minChanges - freqMax
# Return final answer minChanges
   return minChanges
str = "wxyz"  # Given String
n = len(str)  # Getting size of the given string
# Call the function to get minimum number of changes to make left and right rotated string same
res = getMinimumChange(str, n)
# Print result
print(
   "The minimum number of changes to make the left and right rotated string same are: "
)
print(res)

输出

The minimum number of changes to make the left and right rotated string same are: 
2

时间和空间复杂度

上述代码的时间复杂度是O(N)，因为我们同时遍历了字符串和数字。

上述代码的空间复杂度是O(1)，因为没有使用额外的空间来存储任何内容。

其中，N是字符串的大小。

结论

在本教程中，我们实现了一个Python3程序，将字符改变的数量最小化，使得字符串的左右旋转相同。我们采用了哈希的方法来存储频率。时间复杂度为O(N)，空间复杂度为O(1)，其中N是给定字符串的大小。