C++에서 회문의 순열인 최대 짝수 길이 하위 문자열

문제 설명

주어진 문자열이 팰린드롬으로 배열될 수 있는 하위 문자열의 최대 길이를 찾는 것이 작업입니다.

예시

입력 문자열 ="5432112356"이면 최대 회문 부분 문자열이 "321123"이고 길이가 6이므로 답은 6입니다.

알고리즘

• 하위 문자열의 길이가 홀수이면 최종 솔루션에서 고려할 수 없습니다.
• 하위 문자열의 길이가 짝수이면 해당 하위 문자열의 각 문자가 짝수 번 발생해야 사전 수를 사용하여 수행할 수 있는 경우에만 가능한 솔루션이 될 수 있습니다. 각 문자가 짝수번 나오는지 확인합니다. 그렇다면 가능한 솔루션 중 하나로 포함합니다. 그런 다음 단순히 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