จัดเรียงสตริงใหม่เพื่อเพิ่มจำนวนสตริงย่อยพาลินโดรมสูงสุดใน C++

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

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

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

ผลผลิต − การจัดเรียงสตริงใหม่เพื่อเพิ่มจำนวนสตริงย่อยพาลินโดรมสูงสุดคือ:iinnt

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

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

ผลผลิต − การจัดเรียงสตริงใหม่เพื่อเพิ่มจำนวนสตริงย่อยพาลินโดรมสูงสุดคือ:aaaaabbb

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

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

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

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

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

  • ประกาศอาร์เรย์ประเภทจำนวนเต็มขนาด 26 สมมติว่า arr[26] และกำหนดค่าเริ่มต้นด้วย 0

  • ประกาศตัวแปรชั่วคราว 'ชั่วคราว' ของประเภทสตริง

  • เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง i น้อยกว่าความยาว ภายในลูป ให้ตั้งค่า arr[str[i] - 'a']++

  • เริ่มลูป FOR จาก i ถึง 0 จนถึง i น้อยกว่า 26 ภายในลูป ให้เริ่มลูปอื่น FOR จาก j ถึง 0 จนถึง j น้อยกว่า arr[i] ภายในลูป ตั้งค่า temp เป็น temp + (char)(97 + i)

  • อุณหภูมิขากลับ

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

ตัวอย่าง

#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