คำอธิบายปัญหา
กำหนดสตริง งานคือการหาความยาวสูงสุดของซับสตริงที่สามารถเรียงใหม่เป็นพาลินโดรม (Palindrome) ได้
ตัวอย่าง
ถ้าสตริงนำเข้า = "5432112356" คำตอบคือ 6 เพราะพาลินโดรมซับสตริงสูงสุดคือ "321123" และความยาวคือ 6
อัลกอริทึม
- ถ้าความยาวของซับสตริงเป็นคี่ จะไม่สามารถพิจารณาในคำตอบสุดท้ายได้
- ถ้าความยาวของซับสตริงเป็นคู่ จะเป็นคำตอบที่เป็นไปได้ก็ต่อเมื่อตัวอักษรทุกตัวในซับสตริงนั้นเกิดขึ้นจำนวนคู่ (even number of times) ซึ่งสามารถตรวจสอบได้โดยใช้ dictionary count เราตรวจสอบว่าแต่ละตัวอักษรเกิดขึ้นจำนวนคู่หรือไม่ ถ้าใช่ ให้รวมเป็นคำตอบที่เป็นไปได้หนึ่ง จากนั้นเราสร้างซับสตริงถัดไปโดยรวมตัวอักษรถัดไปในสตริง ซึ่งทำได้โดยเพิ่ม end ขึ้นเรื่อยๆ และตรวจสอบแบบเวียนเกิดว่าสามารถสร้างซับสตริงที่ยาวกว่าได้หรือไม่ ซึ่งตรงตามเงื่อนไข และคืนค่าสูงสุดของทุกคำตอบที่เป็นไปได้
ตัวอย่างโค้ด
#include <bits/stdc++.h> using namespace std; unordered_map<int, int> countt; bool isPalindromePossible(unordered_map<int, int> &countt) { for (auto key : countt) { if (key.second & 1) { return false; } return true; } int getMaxPalindrome(string str, unordered_map<int, int> &countt, int start, int end) { if (end == str.length()) { if ((end - start) % 2 == 0) if (isPalindromePossible(countt)) return end - start; return 0; } else { if ((end - start) % 2 == 0) { if (isPalindromePossible(countt)) { countt[str[end]]++; return max(end - start, getMaxPalindrome(str, countt, start, end + 1)); } else { countt[str[end]]++; return getMaxPalindrome(str, countt, start, end + 1); } } else { countt[str[end]]++; unordered_map<int, int> c(countt.begin(), countt.end()); int length = getMaxPalindrome(str, c, start, end + 1); countt[str[end]]--; countt[str[start]]--; return max(length, getMaxPalindrome(str, countt, start + 1, end)); } } } int main(int argc, char const *argv[]) { string str = "5432112356"; int start = 0, end = 0; cout << "Maximum palindrome length = " << getMaxPalindrome(str, countt, start, end) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้:
Maximum palindrome length = 6
