C++: Longest Palindrome

Thought Process

To find the length of the longest palindrome that can be built from a given string, we count the frequency of each character. A palindrome can have at most one character with an odd frequency (the middle character), while all other characters must have even frequencies. We calculate the total number of pairs of characters and check if there is at least one character with an odd frequency. If so, we add 1 to the total length to account for the middle character. 

class Solution {
public:
    int longestPalindrome(string s) {

        int freq[126] = {0};

        for(int i=0;i<s.size();i++){

            int x = s[i];
            freq[x]++;
        }
        bool odd = false;
        int pairs = 0;
        for(int i=0;i<126;i++){

            if(freq[i]%2==1)
                odd = true;

            pairs = pairs + freq[i]/2;
        }
        
        if(odd)
            return 2*pairs + 1;
        else
            return 2*pairs;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the string once to count character frequencies and then iterates through the frequency array, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses a fixed-size frequency array, ensuring constant space usage.

Code copied!