In Chuỗi Gần Nhất Không Chứa Ký Tự Trùng Lặp Keo Cạnh Trong C++

Trong bài toán này, chúng ta được cho một chuỗi. Nhiệm vụ là in ra một chuỗi gần nhất với chuỗi hiện tại và không chứa bất kỳ ký tự trùng lặp kề cạnh nào.

Ví dụ để hiểu vấn đề:

Đầu vào: chuỗi = "good" → Đầu ra: goad

Trong ví dụ này, ta thấy ký tự tại chỉ mục 1 và 2 giống nhau, nên ta thay đổi ký tự tại chỉ mục 2.

Để giải quyết, ta duyệt chuỗi và kiểm tra xem hai ký tự kề cạnh có giống nhau không. Nếu có, thay đổi ký tự thứ hai (nếu i và i+1 giống nhau, thay đổi i+1). Giải pháp sử dụng thuật toán tham lam: với mỗi cặp ký tự kề cạnh trùng lặp, ta thực hiện một lần thay đổi. Lưu ý phải kiểm tra các ký tự xung quanh khi thay đổi: sau khi thay đổi ký tự i, thì ký tự i+1 và i phải khác nhau.

Ví Dụ

Chương trình minh họa giải pháp:

#include <iostream>
#include <string.h>
using namespace std;

void printStringWithNoDuplicates(string str) {
    int len = str.length();
    for (int i = 1; i < len; i++) {
        if (str[i] == str[i - 1]) {
            str[i] = 'a';
            while (str[i] == str[i - 1] || (i + 1 < len && str[i] == str[i + 1]))
                str[i]++;
            i++;
        }
    }
    cout << str;
}

int main() {
    string str = "good";
    cout << "Chuỗi gốc là: " << str << endl;
    cout << "Chuỗi không có ký tự trùng lặp kề cạnh: ";
    printStringWithNoDuplicates(str);
    return 0;
}

Đầu Ra

Chuỗi gốc là: good
Chuỗi không có ký tự trùng lặp kề cạnh là: goad