C++程序最小化更改字符以使字符串左右旋转相同时的字符个数

给定一个由小写英文字母组成的字符串 S ，任务是找到要改变的最少字符数，使得字符串的左旋和右旋相同。

举例：

输入： S = “abcd”

输出： 2

解释：

字符串左移后为：”bcda”

字符串右移后为：”dabc”

将第3个位置上的字符改为 “a”，第4个位置上的字符改为 “b”，字符串变为 “abab”。

因此，左旋和右旋都变为 “baba”。

输入： S = “gfg”

输出： 1

解释：

将位置1上的字符更新为 “g”，字符串变为 “ggg”。

因此，左旋和右旋相同。

解法： 解决该问题的关键观察是，当字符串的长度为偶数时，左旋和右旋相同的字符长度必须为偶数下标上的字符和奇数下标上的字符相同。对于长度为奇数的字符串，所有字符必须相同。按照以下步骤解决该问题：

检查字符串的长度是否为偶数，如果是，则要更改的最小字符数是字符串长度减去最常出现在偶数下标和奇数下标的元素的频率。
否则，如果字符串的长度为奇数，则要更改的最小字符数是字符串长度减去字符串中出现频率最高的字符。
打印获得的最终计数。

以下是上述方法的实现：

// C++程序：
// 以上解法
 
#include <bits/stdc++.h>
using namespace std;
 
// 查找要从中删除的最小字符数
int getMinimumRemoval(string str)
{
    int n = str.length();
 
    // 通过N初始化答案
    int ans = n;
 
    // 如果长度为偶数
    if (n % 2 == 0) {
 
        // 对于奇数和偶数下标的频率数组
        vector<int> freqEven(128);
        vector<int> freqOdd(128);
 
        // 存储偶数和奇数下标的字符频率
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                freqEven[str[i]]++;
            }
            else {
                freqOdd[str[i]]++;
            }
        }
 
        // 存储偶数和奇数下标的最多频率
        int evenMax = 0, oddMax = 0;
 
        for (char chr = 'a'; chr <= 'z'; chr++) {
 
            evenMax = max(evenMax, freqEven[chr]);
            oddMax = max(oddMax, freqOdd[chr]);
        }
 
        // 更新答案
        ans = ans - evenMax - oddMax;
    }
 
    // 如果长度为奇数
    else {
        // 存储字符串的字符频率
        vector<int>freq(128);
        for (int i = 0; i < n; i++) {
            freq[str[i]]++;
        }
 
        // 存储字符串中出现频率最高的字符
        int strMax = 0;
        for (char chr = 'a'; chr <= 'z'; chr++) {
            strMax = max(strMax, freq[chr]);
        }
 
        // 更新答案
        ans = ans - strMax;
    }
 
    return ans;
}
 
// 主方法
int main()
{
    string str = "geeksgeeks";
 
    cout << getMinimumRemoval(str);
}

输出：

时间复杂度： O(N)，因为我们使用循环遍历N次，所以时间成本为O(N)

辅助空间： O(1)，因为我们没有使用任何额外的空间。