Longest Palindrome easy

Problem Statement

Given a string s which consists of lowercase or uppercase letters, find the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

Example 1:

Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a" Output: 1 Explanation: The longest palindrome that can be built is "a", whose length is 1.

Steps

1. Character Count: Create a map (or an array if you know the character range) to count the occurrences of each character in the input string s.

2. Odd Count Check: Iterate through the character counts. Count the number of characters with odd occurrences.

3. Calculate Length: The maximum length of the palindrome will be the sum of all character counts (even counts will form pairs in the palindrome). If there's a character with an odd count, we can use one instance of that character in the middle of the palindrome. Therefore, if the number of characters with odd counts is greater than 0, add 1 to the total length.

Explanation

The key idea is that a palindrome can be formed by pairing up characters. If we have an even number of a character, we can use all of them in the palindrome. If we have an odd number, we can use all but one (placing the single character in the center).

Code (C++)

#include <iostream>
#include <string>
#include <map>

using namespace std;

int longestPalindrome(string s) {
    map<char, int> charCount;
    for (char c : s) {
        charCount[c]++;
    }

    int oddCount = 0;
    int totalLength = 0;
    for (auto const& [key, val] : charCount) {
        totalLength += (val / 2) * 2; // Add the pairs
        if (val % 2 != 0) {
            oddCount++;
        }
    }

    return totalLength + (oddCount > 0 ? 1 : 0);
}

int main() {
    string s1 = "abccccdd";
    string s2 = "a";
    string s3 = "bananas";

    cout << "Longest Palindrome Length for \"" << s1 << "\": " << longestPalindrome(s1) << endl; //Output: 7
    cout << "Longest Palindrome Length for \"" << s2 << "\": " << longestPalindrome(s2) << endl; //Output: 1
    cout << "Longest Palindrome Length for \"" << s3 << "\": " << longestPalindrome(s3) << endl; //Output: 5

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once to count characters, and then iterate through the map (which has at most n entries).

• Space Complexity: O(k), where k is the number of unique characters in the string. In the worst case, k could be n, but typically it's much smaller. The space used by the charCount map dominates the space complexity.