จัดเรียงสตริงใหม่เพื่อเพิ่มจำนวนสตริงย่อยแบบ Palindrome ให้มากที่สุดใน C++

ภาพรวม

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

ตัวอย่าง

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

เอาต์พุต − Rearrangement of the string to maximize the number of palindromic substrings is: iinnt.

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

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

เอาต์พุต − Rearrangement of the string to maximize the number of palindromic substrings is: aaaaabbb.

คำอธิบาย − จัดเรียงตัวอักษรเพื่อให้ได้ Palindrome สูงสุด ผลลัพธ์คือ 'aaaaabbb'

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

• รับสตริง str คำนวณความยาว length
• เรียก Rearr_string(str, length)
• ภายในฟังก์ชัน:
  • สร้างอาร์เรย์ arr[26] เริ่มต้น 0 นับความถี่ตัวอักษร a-z
  • ตัวแปร temp สตริงว่าง
  • วนนับความถี่: arr[str[i]-'a']++
  • วน i=0 ถึง 25 วน j=0 ถึง arr[i]-1 ต่อตัวอักษร (char)(97+i) ลง temp
  • คืนค่า temp (ตัวอักษรเรียงตามลำดับ a-z)
• พิมพ์ผลลัพธ์

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

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

string Rearr_string(string str, int length){ 
    int arr[26] = { 0 }; 
    string temp = ""; 
    for(int i = 0; i < length; i++){ 
        arr[str[i] - 'a']++; 
    } 
    for(int i = 0; i < 26; i++){ 
        for(int j = 0; j < arr[i]; j++){ 
            temp = temp + (char)(97 + i); 
        } 
    } 
    return temp; 
} 

int main(){ 
    string str = "itinn"; 
    int length = str.length(); 
    cout << "Rearrangement of the string to maximize the number of palindromic substrings is: " << Rearr_string(str, length); 
    return 0; 
}

ผลลัพธ์

Rearrangement of the string to maximize the number of palindromic substrings is: iinnt