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

ในปัญหานี้ เราได้รับสตริง งานของเราคือพิมพ์สตริงที่ใกล้เคียงที่สุดกับสตริงปัจจุบันและไม่มีอักขระที่ซ้ำกันที่อยู่ติดกัน

มาดูตัวอย่างทำความเข้าใจปัญหากัน

Input: string = “good”
Output: goad

ในตัวอย่างนี้ เราพบว่าองค์ประกอบที่ดัชนี 1 และ 2 เหมือนกัน ดังนั้นเราจึงเปลี่ยนองค์ประกอบที่ดัชนี 2

เพื่อแก้ปัญหานี้ เราจะสำรวจสตริงและตรวจสอบว่าองค์ประกอบที่อยู่ติดกันสององค์ประกอบเหมือนกันหรือไม่ ถ้าใช่ ให้เปลี่ยนองค์ประกอบที่สอง (หากองค์ประกอบ i และ i+1 เหมือนกัน ให้เปลี่ยนองค์ประกอบ i+1) การแก้ปัญหานี้จะใช้อัลกอริธึมโลภและสำหรับองค์ประกอบที่คล้ายกันแต่ละคู่ที่อยู่ติดกันเราจะทำการเปลี่ยนแปลงหนึ่งรายการ สิ่งหนึ่งที่เราต้องจำไว้คือการตรวจสอบองค์ประกอบที่อยู่ใกล้เคียงทั้งหมดในขณะที่เปลี่ยนแปลง เช่น หากเรากำลังเปลี่ยนองค์ประกอบ ith มากกว่าหลังจากเปลี่ยนองค์ประกอบดัชนี i+1 และ i ควรจะแตกต่างกัน

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันของเรา

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

ผลลัพธ์

The orignal string is : good
String without adjecent duplicate characters is : goad