컨셉
주어진 문자열과 관련하여 문자열에서 문자를 제거하거나 섞어서 형성할 수 있는 가장 긴 회문을 결정합니다. 가장 긴 길이의 회문 문자열이 여러 개 있는 경우 마지막으로 회문 하나만 반환합니다.
입력
pqr
출력
p OR q OR r
입력
ppqqrr
출력
pqrrqp OR qprrpq OR rqppqr OR any other palindromic string of length 6.
입력
pqp
출력
pqp
방법
여기에서 회문 문자열을 be, mid, end의 세 부분으로 나눌 수 있습니다. 홀수 길이의 회문 문자열(예:2n + 1)과 관련하여 여기서 'beg'는 문자열의 처음 n개의 문자로 구성되고 'mid'는 (n + 1)번째 문자를 의미하는 1개의 문자로 구성되며 'end'는 다음의 마지막 n문자로 구성됩니다. 회문 문자열. 짝수 길이 2n의 회문 문자열과 관련하여 '중간'에는 항상 비어 있습니다. 우리는 이미 'end'가 'beg'의 역순으로 string이 회문이라는 것을 알고 있습니다. 이제 개념은 우리 솔루션에서 위의 관찰을 구현하는 것입니다. 문자의 셔플링이 허용되기 때문에 입력 문자열에서 문자의 순서에 관계가 없습니다. 이제 우리는 먼저 입력 문자열에서 각 문자의 빈도를 얻습니다. 그 후 입력 문자열에서 짝수(예:2n)가 발생하는 모든 문자는 출력 문자열의 일부가 됩니다. 왜냐하면 'beg' 문자열에서 n개의 문자를 쉽게 설정하고 'end' 문자열에서 다른 n개의 문자를 설정할 수 있기 때문입니다(보존의 도움으로 회문 순서). 홀수 발생 문자(예:2n + 1)와 관련하여 여기에서는 'mid'를 이러한 모든 문자 중 하나로 채우고 나머지 2n 문자는 반으로 분할하여 시작과 끝에 추가합니다.
예시
// C++ program to find the longest palindrome by removing
// or shuffling characters from the given string
#include <bits/stdc++.h>
using namespace std;
// Shows function to find the longest palindrome by removing
// or shuffling characters from the given string
string findLongestPalindrome(string str1){
// Indicated to stores freq of characters in a string
int count1[256] = { 0 };
// Determine freq of characters in the input string
for (int i = 0; i < str1.size(); i++)
count1[str1[i]]++;
// Shows any palindromic string consisting of three parts
// beg1 + mid1 + end1
string beg1 = "", mid1 = "", end1 = "";
//Here solution assumes only lowercase characters are
// present in string. We can easily extend this
// to consider any set of characters
for (char ch1 = 'a'; ch1 <= 'z'; ch1++){
// Now if the current character freq is odd
if (count1[ch1] & 1){
// Here mid1 will contain only 1 character. It
// will be overridden with next character
// with odd freq
mid1 = ch1;
// Here decrement the character freq to make
// it even and consider current character
// again
count1[ch1--]--;
}
// Here if the current character freq is even
else{
// Now if count is n(an even number), push
// n/2 characters to beg string and rest
// n/2 characters will form part of end
// string
for (int i = 0; i < count1[ch1]/2 ; i++)
beg1.push_back(ch1);
}
}
// Here end will be reverse of beg
end1 = beg1;
reverse(end1.begin(), end1.end());
// Now return palindrome string
return beg1 + mid1 + end1;
}
// Driver code
int main(){
string str1 = "pqqprrs";
cout << findLongestPalindrome(str1);
return 0;
} 출력
pqrsrqp