Palindrome dài nhất trong C ++

Giả sử chúng ta có một chuỗi bao gồm các chữ cái thường hoặc chữ hoa, chúng ta phải tìm độ dài của các palindromes dài nhất có thể được tạo bằng các chữ cái đó. Giờ đây, chuỗi phân biệt chữ hoa chữ thường, vì vậy "Aa" không được coi là một palindrome ở đây.

Vì vậy, nếu đầu vào là "abccccdd", thì đầu ra sẽ là 7, vì một palindrome dài nhất có thể được tạo là "dccaccd", có độ dài là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ mp

• cho mỗi ký tự tôi trong s

  • (tăng mp [i] lên 1)

• ma:=0, c:=0, ans:=0

• cho mỗi cặp khóa-giá trị i trong mp

  • nếu giá trị của imod 2 giống với 1, thì -

    • (tăng ma lên 1)

  • c:=c + giá trị của i

• nếu ma> 0, thì -

  • (giảm ma đi 1)

• ans:=c - ma

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestPalindrome(string s) {
      unordered_map<char, int> mp;
      for (auto i : s)
         mp[i]++;
      int ma = 0, c = 0, ans = 0;
      for (auto i : mp) {
         if ((i.second) % 2 == 1)
            ma++;
         c += i.second;
      }
      if (ma > 0)
         ma--;
      ans = c - ma;
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.longestPalindrome("abccccdd"));
}

Đầu vào

"abccccdd"

Đầu ra

7