จัดเรียงตัวอักษรในสตริงให้ไม่มีตัวอักษรติดกันซ้ำด้วย C++

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

ดูสถานการณ์ Input-Output ต่างๆ

Input - string str = "itinn"

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

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

Input - string str = "abbaabbaa"

Output - Rearrangement of characters in a string such that no two adjacent are same is: ababababa

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

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

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

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

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

• ภายในฟังก์ชัน Rearrangement(arr, length)

  • ตั้งค่าขนาดสตริงเป็น (length + 1) / 2

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

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

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

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

  • ตรวจสอบ IF total มากกว่า size แล้วคืนค่า

  • เริ่มลูป WHILE total แล้วตั้งค่า ptr[temp] = ch, ตั้งค่า temp = temp + 2 และลด total ลง 1

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

  • คืนค่า ptr

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

  • ประกาศตัวแปรจำนวนเต็มเป็น high = 0 และตัวแปร character เป็น 'c'

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

  • คืนค่า c

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

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

#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