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。

方法

在看到上面給定字串的示例之後，讓我們繼續討論方法。

這種方法的思想是基於觀察。觀察有兩個要點：

• 當我們有一個偶數長度的字串時，字串中偶數索引和奇數索引的所有字元必須相同，才能使左右旋轉的字串相同。

• 當我們有一個奇數長度的字串時，字串中的所有字元必須相同，才能使左右旋轉的字串相同。

讓我們看看下面的程式碼，以便更好地理解上述方法。

示例

# 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是給定字串的大小。