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。

方法

在看到上面给定字符串的示例之后,让我们继续讨论方法。

这种方法的思想是基于观察。观察有两个要点:

  • 当我们有一个偶数长度的字符串时,字符串中偶数索引和奇数索引的所有字符必须相同,才能使左右旋转的字符串相同。

  • 当我们有一个奇数长度的字符串时,字符串中的所有字符必须相同,才能使左右旋转的字符串相同。

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

示例

Open Compiler
# 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是给定字符串的大小。

更新于:2023年7月11日

70 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告