LeetCode Tutorial: Longest Palindrome Solution

Logic: Any character with even frequency could be included in palindrome. i.e. AAaaBBbb --> AaBbbBaA In addition, character with odd frequency could be included by ignoring it's one apperance and one char with odd frequency. i.e. AAaaBBbbcccd --> AaBbcccbBaA (OR) AaBbcdcbBaA

Approach: Calculate freqeuncy of each character. For even frequency, add it to the total. For odd frequency, ignore it's one apperance, now this is also char with even frequency, add freq-1 to the total. We can have one char with odd frequncy so add 1 to the total. (If char with odd frequency are there.)

Code:

class Solution {public: int longestPalindrome(string s) { int freq[52]={0},total=0,flag=0; for(int i=0;i<s.length();i++){ if(s[i]>='a') freq[s[i]-'a'+26]++; else freq[s[i]-'A']++; } for(int i=0;i<52;i++){ if(freq[i]%2){ total+=freq[i]-1; flag=1; } else total+=freq[i]; } if(flag) total+=1; return total; } };