在給定字串中插入最少字元以移除相鄰重複字元

---

在這個問題中，我們將計算需要插入的最小字元數，以移除所有相鄰的重複字元。

為了解決這個問題，我們需要計算相鄰重複字元對的總數。

問題陳述 – 我們給定一個名為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迴圈遍歷字串，並計算從給定字串中移除所有相鄰重複項所需的最小插入次數。