Longest Palindrome easy

Problem Statement

Given a string s which consists of lowercase or uppercase letters, return 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 Frequency Count: Create a dictionary (or hash map) to store the frequency of each character in the input string s.

2. Odd and Even Count: Iterate through the dictionary. Keep track of the total length of characters with even frequencies and the count of characters with odd frequencies.

3. Calculate Longest Palindrome Length: The longest palindrome can be formed by using all characters with even frequencies and at most one character with an odd frequency (placed in the middle). The length is the sum of twice the count of even frequency characters plus 1 (if there's a character with an odd frequency).

Explanation

A palindrome is a sequence that reads the same backward as forward. To construct the longest palindrome from a given set of characters, we need to maximize the number of characters that can be paired. Characters with even frequencies can all be paired, forming the core of the palindrome. At most one character with an odd frequency can be placed in the center of the palindrome. Any extra characters with odd frequencies cannot contribute to the palindrome's length.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestPalindrome(string s) {
        Dictionary<char, int> charCount = new Dictionary<char, int>();

        // Count character frequencies
        foreach (char c in s) {
            if (charCount.ContainsKey(c)) {
                charCount[c]++;
            } else {
                charCount[c] = 1;
            }
        }

        int evenCount = 0;
        int oddCount = 0;

        // Categorize characters based on frequency
        foreach (int count in charCount.Values) {
            if (count % 2 == 0) {
                evenCount += count;
            } else {
                oddCount++;
            }
        }

        // Calculate the length of the longest palindrome
        int maxLength = evenCount; 
        if (oddCount > 0) {
            maxLength += 1; // Add one character from odd frequency characters for the center
        }

        return maxLength;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input string. This is because iterating through the string and the dictionary takes linear time.
• Space Complexity: O(k), where k is the number of unique characters in the string. In the worst case, k could be n (all characters are unique), but usually k is much smaller than n. The space used is dominated by the dictionary to store character frequencies.