输出 

0

解释– 该字符串不包含任何相邻的重复字符。因此，我们不需要在其中插入任何字符。

输入

str = 'ppppppp'

输出

6

解释– 该字符串的所有字符都相同。因此，我们需要在字符串中插入长度为 1 的字符。

方法 1

此方法将计算字符串中相邻重复字符的总数。最终计数即为答案，因为我们需要在每个相邻的重复字符之间插入一个新字符。

算法

步骤 1 – 使用字符串大小初始化 str_size 变量。

步骤 2 – 另外，声明并用 0 初始化 total_steps 变量，用于存储字符串中的最小插入次数。

步骤 3 – 使用 for 循环开始遍历字符串。

步骤 4 – 如果第 p 个索引处的字符与第 (p - 1) 个索引处的字符相同，则将 total_Steps 加 1。

步骤 5 – 最后，返回 total_steps。

示例

#include <iostream>
using namespace std;

int totalInsertions(string alpha) {
    // 字符串长度
    int str_size = alpha.size();
    // 存储加法次数
    int total_steps = 0;
    // 迭代字符串
    for (int p = 1; p < str_size; p++) {
        if (alpha[p] == alpha[p - 1])
        total_steps++;
    }
    // 返回加法次数
    return total_steps;
}
int main() {
    string str = "ccddrt";
    cout << "删除相邻重复项所需的总添加次数为 - " << totalInsertions(str);
    return 0;
}

输出

删除相邻重复项所需的总添加次数为 - 2

时间复杂度 – 迭代字符串，复杂度为 O(N)。

空间复杂度 – 因为我们不使用动态空间，所以复杂度为 O(1)。

上述问题与查找给定字符串中相邻重复字符的总数非常相似。这两个问题的解决方案相同。程序员还可以尝试使用 while 循环遍历字符串，并计算从给定字符串中删除所有相邻重复字符所需的最少插入次数。

相关文章

打印 下一节 ❯❮ 上一节