จัดเรียงอักขระใหม่ในสตริงโดยที่ไม่มีสองตัวที่อยู่ติดกันเหมือนกันใน C++

เราได้รับสตริง สมมติว่า str ของความยาวที่กำหนด งานคือการจัดเรียงสตริงที่กำหนดใหม่ในลักษณะที่จะไม่มีอักขระที่อยู่ติดกันเดียวกันที่จัดเรียงเข้าด้วยกันในสตริงผลลัพธ์

ให้เราดูสถานการณ์อินพุตเอาต์พุตที่หลากหลายสำหรับสิ่งนี้ -

ป้อนข้อมูล − string str ="itnn"

ผลผลิต − การจัดเรียงอักขระใหม่ในสตริงโดยที่ไม่มีสองตัวที่อยู่ติดกันเหมือนกันคือ:initn

คำอธิบาย − เราได้รับตัวแปรประเภทสตริง สมมติว่า str ตอนนี้ เราจะจัดเรียงอักขระของสตริงอินพุตใหม่ในลักษณะที่ไม่มีอักขระสองตัวที่เหมือนกันเกิดขึ้นที่ตำแหน่งเดียวกัน เช่น เลื่อน 'nn' เนื่องจากอักขระเหล่านั้นเหมือนกันและอยู่ติดกัน ดังนั้นสตริงสุดท้ายจะเป็น 'initn'

ป้อนข้อมูล − string str ="abbaabbaa"

ผลผลิต − การจัดเรียงอักขระใหม่ในสตริงโดยที่ไม่มีสองตัวที่อยู่ติดกันคือ:ababababa

คำอธิบาย − เราได้รับตัวแปรประเภทสตริง สมมติว่า str ตอนนี้ เราจะจัดเรียงอักขระของสตริงอินพุตใหม่ในลักษณะที่ไม่มีอักขระสองตัวที่เหมือนกันเกิดขึ้นที่ตำแหน่งเดียวกัน เช่น ขยับ 'bb', 'aa', 'bb', 'aa' เพราะมันเหมือนกันและอยู่ติดกัน อื่นๆ. ดังนั้นสตริงสุดท้ายจะเป็น 'ababababa'

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ป้อนตัวแปรประเภทสตริง สมมติว่า str และคำนวณขนาดของสตริงและเก็บไว้ในความยาวที่ตั้งชื่อตัวแปร

• ตรวจสอบว่า IF length เป็น 0 แล้วส่งคืน

• ส่งข้อมูลไปยังฟังก์ชัน Rearrangement(str, length)

• ภายในฟังก์ชัน การจัดเรียงใหม่ (arr, length)

  • กำหนดขนาดของสตริงด้วย (length + 1)/2.

  • ประกาศตัวแปรประเภทเวกเตอร์เป็น vec(26, 0) ที่จะเก็บข้อมูลประเภทจำนวนเต็มและ ptr ของประเภทสตริงเป็น ptr(ความยาว, '') ตัวแปรชั่วคราวของจำนวนเต็มประเภทเป็น 0

  • เริ่มวนซ้ำ FOR เพื่อวนซ้ำ str ผ่านมัน ภายในลูป ให้ตั้งค่า vec[it - 'a']++

  • สร้างตัวแปรประเภทอักขระเป็น ch และตั้งค่าด้วยการเรียกฟังก์ชัน maximum(vec)

  • ประกาศตัวแปรประเภทจำนวนเต็มเป็นผลรวมและตั้งค่าด้วย vec[ch - 'a']

  • ตรวจสอบว่าผลรวมมากกว่าขนาดแล้วส่งคืน

  • เริ่มวนซ้ำ WHILE Total จากนั้นตั้งค่า ptr[temp] เป็น ch ตั้งค่า temp เป็น temp + 2 และลดจำนวนรวมลง 1

  • ตั้งค่า vec[ch - 'a'] เป็น 0 เริ่มลูป FOR จาก i ถึง 0 จนถึง i น้อยกว่า 26 ภายในลูป ให้เริ่มในขณะที่ vec[i] มากกว่า 0 ตั้งค่า temp เป็น (temp> =length) ? 1 :temp และ ptr[temp] ถึง 'a' + i และ temp to temp + 2 และลด vec[i] ลง 1

  • กลับ ptr

• ภายในฟังก์ชัน char maximum(const vector&vec)

  • ประกาศตัวแปรประเภทจำนวนเต็มสูงถึง 0 และตัวแปรประเภทอักขระเป็น 'c'

  • เริ่มลูป FOR จาก i ถึง 0 จนถึง i น้อยกว่า 26 ภายในลูป ให้ตรวจสอบว่า vec[i] น้อยกว่า high แล้วตั้งค่า high เป็น vec[i] และ c เป็น 'a' + i.

  • กลับค

• พิมพ์ผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
char maximum(const vector<int>& vec){
   int high = 0;
   char c;
   for(int i = 0; i < 26; i++){
      if(vec[i] > high){
         high = vec[i];
         c = 'a' + i;
      }
   }
   return c;
}
string Rearrangement(string str, int length){
   int size = (length + 1) / 2;
   vector<int> vec(26, 0);
   string ptr(length, ' ');
   int temp = 0;
   for(auto it : str){
      vec[it - 'a']++;
   }
   char ch = maximum(vec);
   int total = vec[ch - 'a'];
   if(total > size){
      return "";
   }
   while(total){
      ptr[temp] = ch;
      temp = temp + 2;
      total--;
   }
   vec[ch - 'a'] = 0;
   for(int i = 0; i < 26; i++){
      while (vec[i] > 0){
         temp = (temp >= length) ? 1 : temp;
         ptr[temp] = 'a' + i;
         temp = temp + 2;
         vec[i]--;
      }
   }
   return ptr;
}
int main(){
   string str = "itinn";
   int length = str.length();
   if(length == 0){
      cout<<"Please enter a valid string";
   }
   string count = Rearrangement(str, length);
   if(count == ""){
      cout<<"Please enter a valid string";
   }
   else{
      cout<<"Rearrangement of characters in a string such that no two adjacent are same is: "<<count;
   }
   return 0;
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

Rearrangement of characters in a string such that no two adjacent are same is: initn