Tuyên bố vấn đề
Cho một chuỗi, nhiệm vụ là tìm độ dài tối đa của chuỗi con của chuỗi đó có thể được sắp xếp thành một Palindrome.
Ví dụ
Nếu input string =“5432112356” thì câu trả lời là 6 vì chuỗi con palindrome tối đa là “321123” và độ dài của nó là 6
Thuật toán
- Nếu độ dài của chuỗi con là lẻ thì nó không thể được xem xét trong các giải pháp cuối cùng.
- Nếu độ dài của chuỗi con là chẵn, thì nó có thể là một giải pháp khả thi chỉ khi mỗi ký tự trong chuỗi con đó xảy ra số lần chẵn có thể được thực hiện bằng cách sử dụng số từ điển. Chúng tôi kiểm tra xem mỗi ký tự có xuất hiện số lần chẵn hay không. Nếu có, thì chúng tôi đưa nó vào như một trong những giải pháp khả thi. Sau đó, chúng tôi tạo chuỗi con tiếp theo bằng cách bao gồm ký tự tiếp theo trong chuỗi, điều này có thể được thực hiện bằng cách đơn giản tăng kết thúc và kiểm tra đệ quy xem chuỗi con có độ dài lớn hơn có thể được hình thành thỏa mãn các điều kiện đã cho hay không và trả về giá trị lớn nhất có thể giải pháp
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Maximum palindrome length = 6