พิมพ์สตริงที่ใกล้เคียงที่สุดโดยไม่มีตัวอักษรซ้ำติดกันใน C++

ภาพรวมปัญหา

ได้รับสตริงหนึ่ง ต้องพิมพ์สตริงที่ใกล้เคียงที่สุดกับสตริงเดิม แต่ไม่มีตัวอักษรซ้ำกันติดกัน

ตัวอย่าง

Input: "good" 
Output: "goad"

ในตัวอย่าง ตัวอักษรที่ index 1 และ 2 เหมือนกัน (o) จึงเปลี่ยนตัวที่ index 2

วิธีแก้ปัญหา (Greedy Algorithm)

1. ลูปผ่านสตริง ตรวจสอบคู่ตัวอักษรติดกัน
2. ถ้าพบตัวอักษรซ้ำ (index i และ i+1 เหมือนกัน) → เปลี่ยนตัวที่ i+1
3. เลือกตัวอักษรใหม่เริ่มจาก 'a' โดยให้ต่างจากตัวก่อนหน้าและตัวถัดไป (ถ้ามี)
4. ข้ามไป index ถัดไปหลังเปลี่ยนแล้ว

ตัวอย่างโค้ด C++

#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 << "The original string is: " << str << endl;
    cout << "String without adjacent duplicate characters is: ";
    printStringWithNoDuplicates(str);
    return 0;
}

ผลลัพธ์ (Output)

The original string is: good
String without adjacent duplicate characters is: goad