C++ 最小插入次数以删除相邻重复的字符

在这个问题中，我们将计算我们需要插入的最小字符数，以删除所有相邻重复的字符。

为了解决这个问题，我们需要计算相邻重复字符对的总数。

问题陈述 - 我们已经给定了一个名为str的字符串，其中包含N个字母字符。我们需要找出我们需要添加到字符串中的不同字符的总数，这样生成的字符串不应包含任何相邻的重复字符。

示例示例

输入

str = "ccddrt"

输出

2

解释 – 我们需要在“cc”之间插入一个字符，在“dd”之间插入一个字符。

输入

str = ‘abcdefrt’

输出

0

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

Input

str = ‘ppppppp’

输出结果

6

说明 – 字符串中的所有字符都相同。因此，我们需要进行字符串长度 – 1 次插入。

方法1

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

算法

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

第2步 – 还要声明和初始化 total_steps 变量为0，以存储对字符串的最小插入次数。

第3步 – 使用 for 循环遍历字符串。

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

第5步 – 最后，返回 total_steps。

示例

#include <iostream>
using namespace std;

int totalInsertions(string alpha) {
    // srting lenght
    int str_size = alpha.size();
    // to store additions
    int total_steps = 0;
    // Iterate the string
    for (int p = 1; p < str_size; p++) {
        if (alpha[p] == alpha[p - 1])
            total_steps++;
    }
    // return count of additions
    return total_steps;
}
int main() {
    string str = "ccddrt";
    cout << "The total number of additions required to remove adjacent duplicates is - " << totalInsertions(str);
    return 0;
}

输出

The total number of additions required to remove adjacent duplicates is - 2

时间复杂度 – 遍历字符串的时间复杂度为 O(N)。

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

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