在给定字符串中插入最少字符以移除相邻重复字符

---

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

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

问题陈述 – 我们给定一个名为str的字符串，其中包含N个字母字符。我们需要找到需要添加到字符串中的不同字符的总数，以便生成的字符串不包含任何相邻的重复字符。

示例

输入

str = "ccddrt"

输出

2

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

输入

str = ‘abcdefrt’

输出

0

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

输入

str = ‘ppppppp’

输出

6

解释 – 字符串的所有字符都相同。因此，我们需要进行字符串长度 - 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) {
    // 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循环遍历字符串，并计算从给定字符串中移除所有相邻重复项所需的最小插入次数。