Tìm palindrome dài nhất bằng cách xóa hoặc xáo trộn ký tự từ chuỗi trong C++

Khái niệm

Cho một chuỗi, tìm palindrome dài nhất có thể tạo thành bằng cách xóa hoặc xáo trộn các ký tự từ chuỗi. Trả về chỉ một palindrome nếu có nhiều palindrome cùng độ dài lớn nhất.

Đầu vào

pqr

Đầu ra

p HOẶC q HOẶC r

Đầu vào

ppqqrr

Đầu ra

pqrrqp HOẶC qprrpq HOẶC rqppqr HOẶC bất kỳ chuỗi palindrome nào độ dài 6.

Đầu vào

pqp

Đầu ra

pqp

Phương pháp

Mọi chuỗi palindrome có thể chia thành ba phần: beg (đầu), mid (giữa), end (cuối). Với palindrome độ dài lẻ 2n+1: 'beg' gồm n ký tự đầu, 'mid' gồm 1 ký tự (ký tự thứ n+1), 'end' gồm n ký tự cuối. Với palindrome độ dài chẵn 2n, 'mid' luôn rỗng. Ta biết 'end' sẽ là đảo ngược của 'beg' để chuỗi thành palindrome.

Vì cho phép xáo trộn ký tự, thứ tự ký tự trong chuỗi đầu vào không quan trọng. Ta đếm tần suất mỗi ký tự. Các ký tự có tần suất chẵn (2n) sẽ tham gia vào chuỗi kết quả: n ký tự cho 'beg' và n ký tự cho 'end'. Các ký tự có tần suất lẻ (2n+1): điền 'mid' bằng một trong các ký tự đó, 2n ký tự còn lại chia đôi thêm vào đầu và cuối.

Ví dụ

// Chương trình C++ tìm palindrome dài nhất bằng cách xóa/xáo trộn ký tự
#include <bits/stdc++.h>
using namespace std;

// Hàm tìm palindrome dài nhất
string findLongestPalindrome(string str1){
    // Lưu tần suất ký tự
    int count1[256] = { 0 };
    // Đếm tần suất
    for (int i = 0; i < str1.size(); i++)
        count1[str1[i]]++;
    // Palindrome gồm 3 phần: beg1 + mid1 + end1
    string beg1 = "", mid1 = "", end1 = "";
    // Giả sử chỉ có ký tự chữ thường, có thể mở rộng cho ký tự khác
    for (char ch1 = 'a'; ch1 <= 'z'; ch1++){
        // Nếu tần suất lẻ
        if (count1[ch1] & 1){
            // mid1 chỉ chứa 1 ký tự, sẽ bị ghi đè bởi ký tự lẻ tiếp theo
            mid1 = ch1;
            // Giảm tần suất để thành chẵn và xét lại ký tự này
            count1[ch1--]--;
        }
        // Nếu tần suất chẵn
        else{
            // Nếu tần suất là n (số chẵn), đẩy n/2 ký tự vào beg, n/2 còn lại vào end
            for (int i = 0; i < count1[ch1]/2 ; i++)
                beg1.push_back(ch1);
        }
    }
    // end là đảo ngược của beg
    end1 = beg1;
    reverse(end1.begin(), end1.end());
    // Trả về chuỗi palindrome
    return beg1 + mid1 + end1;
}

// Chương trình chính
int main(){
    string str1 = "pqqprrs";
    cout << findLongestPalindrome(str1);
    return 0;
}

Đầu ra

pqrsrqp