关于#替换字母#的问题，如何解决？(语言-c++)

Question

时间：1s 空间：256M
题目描述：
有长度为 n 的字符串，仅包含小写字母。

小信想把字符串变成只包含一种字母。他每次可以选择一种字符 c，然后把长度最多为 m 的子串中的字符都替换成 c。

小信想知道最少需要操作几次能让字符串只包含一种字母。

输入格式：
第一行包含两个整数 n, m。

第二行包含一个长度为 n 的字符串，只有小写字符。

输出格式：
对于每组测试数据，输出一个整数表示答案。

样例1输入：
5 4
abcab
样例1输出：
1
样例2输入：
5 3
abcab
样例2输出：
2
约定与提示：
对于100%的数据，1≤m≤n≤2⋅105。

对于样例1：把子串 [1,4] 中的字符都变成 'b'，或者把子串 [2,5] 中的字符都变成 'a'。

Answer 1

回答引自chatgpt

#include <iostream>
#include <cstring>
using namespace std;
const int N = 200010;
int n, m;
char str[N];
int cnt[26];
int main()
{
    cin >> n >> m >> str ;
    int maxv = 0;
    for (int i = 1, j = 0; i <= n; i ++ )
    {
        cnt[str[i] - 'a'] ++ ;
        while (i - j > m || cnt[str[i] - 'a'] + m < i - j + 1)
        {
            cnt[str[j] - 'a'] -- ;
            j ++ ;
        }
        maxv = max(maxv, i - j);
    }
    cout << n - maxv << endl;
    return 0;
}

Answer 2

望采纳回答

Answer 3

以下答案由GPT-3.5大模型与博主波罗歌共同编写：
解题思路：

我们可以枚举所有的种类，以当前枚举到的种类为最后留下的字母，把所有跟它不同的字母换成它，用当前方案的操作步数，更新最优解 ans。

核心代码：

C++ 代码
如果我的回答解决了您的问题，请采纳！

Answer 4

参考GPT和自己的思路：这道题可以使用双指针的思路来解决，具体做法如下：

从左到右遍历字符串，维护一个区间 [l, r]，表示以 s[r] 为结尾的长度最大为 m 的子串。

如果 s[r] 与 s[l] 不同，则需要将该区间中的所有字符替换成 s[r]，并将区间向右移动一位，即令 l = r，r = r + 1。

如果 s[r] 与 s[l] 相同，则令 r = r + 1。

在遍历过程中，记录替换的次数，最后输出即可。

下面是 C++ 的代码实现：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2e5 + 10;

int n, m;
char s[N];

int main()
{
    cin >> n >> m;
    cin >> s;

    int l = 0, r = 0;
    int res = n;
    while (r < n)
    {
        if (r - l + 1 <= m) res = min(res, max(1, r - l + 1) - (r - l + 1));
        else
        {
            if (s[r] != s[l])
            {
                res = min(res, max(1, r - l) - (r - l));
                l++;
            }
            else r++;
        }
    }

    cout << res << endl;

    return 0;
}

代码中，用 res 记录替换的次数，初始值为字符串长度 n，即最坏情况下每个字符都需要替换一次。

在遍历字符串的过程中，如果当前区间长度不超过 m，则直接将替换次数减去区间长度，即将该区间中的所有字符替换成 s[r]。

如果当前区间长度超过 m，则需要将左端点 l 向右移动一位，即将区间缩小，并将替换次数减去区间长度减一，因为除了 s[r] 以外的字符都需要替换成 s[r]。

遍历结束后，输出最终的替换次数即可。

Answer 5

参考GPT的回答和自己的思路，以下是满足你需求的实现代码：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 2e5 + 10;

int n, m;
char s[N];

int main()
{
    cin >> n >> m;
    cin >> s + 1;  // 从下标 1 开始读入字符串

    int ans = n;
    for (char c = 'a'; c <= 'z'; c++)
    {
        int cnt = 0, res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (s[i] == c) cnt++;
            else
            {
                res += (cnt + m - 1) / m;  // 计算需要操作的次数
                cnt = 0;
            }
        }
        res += (cnt + m - 1) / m;
        ans = min(ans, res);
    }

    cout << ans << endl;

    return 0;
}

代码思路：

首先读入字符串，并用一个变量 ans 记录当前的最小操作次数，初始化为字符串的长度。

然后枚举每一种可能的字符，对于每种字符，遍历一遍字符串，统计该字符在字符串中出现的次数，并计算需要多少次操作才能把该字符替换到字符串中的每个位置。

具体来说，我们用变量 cnt 统计当前位置之前该字符出现的次数，如果当前位置的字符不是该字符，就把 cnt 累加到答案中，并将 cnt 清零。

回答不易，还请采纳！！！

Answer 6

枚举每一个字母，用贪心法（遍历字符串，遇到与选择的字母相同的字母，跳过，否则覆写一次）计算覆写次数，求出最小值。

#include<stdio.h>
#include<set>

char str[200001];

int main(){
    std::set<char> s;
    std::set<char>::iterator it;
    int n,m,i,j,min=(unsigned int)-1>>1;//min初始化为int类型最大值
    //输入 
    scanf("%d%d\n",&n,&m); 
    for(i=0;i<n;i++){
        str[i]=getchar();
        s.insert(str[i]);//将输入的字符插入集合，用于确定字符串中存在哪些字符 
    }
    str[i]='\0';
    //外层循环遍历集合中所有字符 
    for(it=s.begin();it!=s.end();it++){
        //循环内求出每种字符对应的覆写次数j 
        j=0;
        for(i=0;i<n;i+=m,j++){//i+=m与j++结合，相当于覆写了一次 
            while(str[i]==*it)i++;//与选择的字符相同，跳过 
            if(i>=n)break; 
        }
        if(j<min)min=j;
    }
    printf("%d",min);
}

测试样例

Answer 7

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7660677

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^