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 HashMap (or similar data structure) to store the frequency of each character in the input string s.

2. Odd and Even Counts: Iterate through the HashMap. Keep track of the total length of characters with even frequencies and the existence of at least one character with an odd frequency.

3. Calculate Length: The length of the longest palindrome is the sum of the characters with even frequencies, plus 1 (if a character with an odd frequency exists). This 'plus 1' accounts for the middle character of the palindrome (a palindrome can have at most one character with an odd frequency).

Explanation

The key idea is that a palindrome can only be constructed using characters that appear an even number of times (they can be paired up) and at most one character with an odd number of times (this character will be the middle character of the palindrome). If a character has an odd frequency, we use all but one instance. The remaining characters form pairs to construct the palindrome.

For example, in "abccccdd," 'c' and 'd' have even frequencies (4 and 2 respectively), and 'a' and 'b' have odd frequencies (1 each). We can use all 'c's and 'd's to create pairs for the palindrome, and we can use one 'a' (or one 'b') as the middle character. The total length would be 4 + 2 + 1 = 7.

Code

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        int evenLength = 0;
        boolean oddExists = false;
        for (int count : charCount.values()) {
            if (count % 2 == 0) {
                evenLength += count;
            } else {
                evenLength += count - 1;
                oddExists = true;
            }
        }

        return evenLength + (oddExists ? 1 : 0);
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the string. This is because we iterate through the string once to count character frequencies and then iterate through the HashMap (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 (if all characters are unique), but in most cases, k will be much smaller than n. The HashMap stores the character counts.