จัดเรียงตัวอักษรให้เป็น Palindrome หากเป็นไปได้ใน C++

ภาพรวม

ได้รับสตริง str ความยาวเท่าใดก็ตาม งานคือจัดเรียงตัวอักษรใหม่ให้เป็นสตริง Palindrome โดยไม่เพิ่มหรือลบตัวอักษร Palindrome คือสตริงที่อ่านจากหน้าหลังได้เหมือนกัน

ตัวอย่าง

อินพุต − string str = "itnin"

เอาต์พุต − Rearrangement of characters to form palindrome if possible is: nitin

คำอธิบาย − จัดเรียงตัวอักษรให้เป็น Palindrome หากไม่ได้คืน "NOT POSSIBLE" ผลลัพธ์คือ 'nitin'

อินพุต − string str = "baaaba"

เอาต์พุต − Rearrangement of characters to form palindrome if possible is: aabbaa

คำอธิบาย − จัดเรียงตัวอักษรให้เป็น Palindrome ผลลัพธ์คือ 'aabbaa'

แนวทางการแก้ปัญหา

• รับสตริง str คำนวณความยาว length
• เรียก Rearrangement(str, length)
• ภายในฟังก์ชัน:
  • สร้าง unordered_map um นับความถี่ตัวอักษร
  • ตัวแปร total = 0 นับตัวอักษรที่มีความถี่คี่
  • ตัวแปร ch เก็บตัวอักษรที่มีความถี่คี่
  • สตริง str_1, str_2 สำหรับสร้างครึ่งหน้าและครึ่งหลัง
  • วนนับความถี่ใน um
  • วนตรวจสอบ um หาก it.second % 2 != 0 เพิ่ม total เก็บ ch = it.first
  • หาก total > 1 หรือ total == 1 && length % 2 == 0 คืน 0 (ไม่ได้)
  • วนสร้างครึ่งหน้า/หลัง: string s(it.second/2, it.first); str_1 += s; str_2 = s + str_2;
  • หาก total == 1 คืน str_1 + ch + str_2 มิฉะนั้น คืน str_1 + str_2
• พิมพ์ผลลัพธ์

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

#include <bits/stdc++.h> 
using namespace std; 

string Rearrangement(string str, int length){ 
    unordered_map<char, int> um; 
    int total = 0; 
    char ch; 
    string str_1 = ""; 
    string str_2 = ""; 
    for (int i = 0; i < length; i++){ 
        um[str[i]]++; 
    } 
    for(auto it : um){ 
        if(it.second % 2 != 0){ 
            total++; 
            ch = it.first; 
        } 
    } 
    if(total > 1 || (total == 1 && length % 2 == 0)){ 
        return "0"; // NOT POSSIBLE 
    } 
    for(auto it : um){ 
        string s(it.second / 2, it.first); 
        str_1 = str_1 + s; 
        str_2 = s + str_2; 
    } 
    if(total == 1){ 
        return str_1 + ch + str_2; 
    } else { 
        return str_1 + str_2; 
    } 
} 

int main(){ 
    string str = "itnin"; 
    int length = str.size(); 
    cout << "Rearrangement of characters to form palindrome if possible is: " << Rearrangement(str, length); 
    return 0; 
}

ผลลัพธ์

Rearrangement of characters to form palindrome if possible is: nitin