สมมติว่าเรามีสตริงที่ประกอบด้วยอักษรตัวพิมพ์เล็กหรือตัวพิมพ์ใหญ่ เราต้องหาความยาวของพาลินโดรมที่ยาวที่สุดที่สามารถสร้างด้วยตัวอักษรเหล่านั้นได้ ตอนนี้สตริงคำนึงถึงขนาดตัวพิมพ์ ดังนั้น "Aa" จึงไม่ถือว่าเป็นพาลินโดรมที่นี่
ดังนั้น หากอินพุตเป็นเหมือน "abccccdd" เอาต์พุตจะเป็น 7 เนื่องจากพาลินโดรมที่ยาวที่สุดตัวหนึ่งที่สร้างได้คือ "dccaccd" ซึ่งมีความยาวเท่ากับ 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่ง mp mp
-
สำหรับแต่ละอักขระ i ใน s
-
(เพิ่ม mp[i] ขึ้น 1)
-
-
ma :=0, c :=0, ans :=0
-
สำหรับแต่ละคู่คีย์-ค่า i เป็น mp
-
ถ้าค่าของ imod 2 เท่ากับ 1 แล้ว −
-
(เพิ่ม ma ขึ้น 1)
-
-
c :=c + ค่าของ i
-
-
ถ้า ma> 0 แล้ว −
-
(ลดลงมา 1)
-
-
ตอบ :=c - ma
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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"));
} อินพุต
"abccccdd"
ผลลัพธ์
7
