คำชี้แจงปัญหา
กำหนดสตริง ภารกิจคือการค้นหาความยาวสูงสุดของสตริงย่อยที่สามารถจัดเรียงเป็นพาลินโดรมได้
ตัวอย่าง
หากอินพุตสตริง =“5432112356” คำตอบคือ 6 เนื่องจากสตริงย่อย palindrome สูงสุดคือ “321123” และความยาวของมันคือ 6
อัลกอริทึม
- หากความยาวของสตริงย่อยเป็นเลขคี่ จะไม่สามารถพิจารณาในคำตอบสุดท้ายได้
- หากความยาวของสตริงย่อยเป็นเลขคู่ อาจเป็นวิธีแก้ปัญหาได้ก็ต่อเมื่ออักขระแต่ละตัวในสตริงย่อยนั้นเกิดขึ้นเป็นจำนวนคู่เท่ากัน ซึ่งสามารถทำได้โดยใช้การนับพจนานุกรม เราตรวจสอบว่าอักขระแต่ละตัวเกิดขึ้นเป็นจำนวนเท่ากันหรือไม่ ถ้าใช่ เราจะรวมไว้เป็นหนึ่งในวิธีแก้ปัญหาที่เป็นไปได้ จากนั้นเราสร้างสตริงย่อยถัดไปโดยรวมอักขระถัดไปในสตริงซึ่งสามารถทำได้โดยเพียงแค่เพิ่มจุดสิ้นสุดและตรวจสอบซ้ำ ๆ ว่าสามารถสร้างสตริงย่อยที่มีความยาวมากกว่าซึ่งเป็นไปตามเงื่อนไขที่กำหนดและคืนค่าสูงสุดที่เป็นไปได้ทั้งหมด โซลูชั่น
ตัวอย่าง
#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
