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