# Longest Palindrome
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/longest-palindrome
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Hash Table, String
**Companies:** [Akamai](https://scaleengineer.com/companies/akamai), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [HP](https://scaleengineer.com/companies/hp)
---
## Problem
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.

**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.

**Constraints:**

* `1 <= s.length <= 2000`
* `s` consists of lowercase **and/or** uppercase English letters only.

# Approaches
## Using a HashMap to Count Frequencies
This approach involves using a `HashMap` to store the frequency of each character in the input string. We iterate through the string once to populate the map. Then, we iterate through the map's values (the character counts) to construct the length of the longest palindrome based on the counts.
**Time:** O(N), where N is the length of the string `s`. Populating the HashMap requires iterating through the string once. Iterating through the map's values takes O(K) time, where K is the number of unique characters (a constant, at most 52). · **Space:** O(K), where K is the number of unique characters in the string. Since the problem specifies lowercase and uppercase English letters, K is at most 52. Therefore, the space complexity is effectively O(1).
**Pros:** The logic is straightforward and easy to understand.; It is a general solution that works for any character set (e.g., Unicode), not just English letters.
**Cons:** Has higher overhead compared to using a simple array due to the costs of hashing and `Map.Entry` object creation.; Requires two passes: one over the string to build the map, and another over the map's values to calculate the length.
### Explanation
The core idea is that a palindrome is built from pairs of characters, with at most one unique character in the center. We can count the occurrences of each character to determine how many pairs can be formed.

1.  We create a `HashMap<Character, Integer>` to store the counts of each character.
2.  We loop through the input string `s`. For each character, we update its count in the map.
3.  After counting, we initialize a variable `length` to 0 and a boolean flag `oddFound` to `false`.
4.  We iterate through the counts in the map. For each count `c`:
    *   We add the largest even number less than or equal to `c` to our `length`. This is done by adding `c` if `c` is even, or `c - 1` if `c` is odd.
    *   If we encounter any character with an odd count, we set the `oddFound` flag to `true`.
5.  Finally, if `oddFound` is `true`, it means we have at least one leftover character that can be placed in the center of the palindrome. We add 1 to the total `length`.
6.  The final `length` is the answer.

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

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

        int length = 0;
        boolean oddFound = false;
        for (int count : counts.values()) {
            if (count % 2 == 0) {
                length += count;
            } else {
                length += count - 1;
                oddFound = true;
            }
        }

        if (oddFound) {
            length++;
        }

        return length;
    }
}
```
### Algorithm
- Initialize a `HashMap<Character, Integer>` to store character frequencies.
- Iterate through the input string `s` and populate the frequency map. For each character `c`, increment its count in the map.
- Initialize `length = 0` and a boolean flag `oddFound = false`.
- Iterate through the values (frequencies) of the map.
- For each frequency `count`, if it's even, add the full `count` to `length`. If it's odd, add `count - 1` to `length` and set `oddFound` to `true`.
- After the loop, if `oddFound` is `true`, it means we can place a single character in the center of the palindrome, so we increment `length` by 1.
- Return the final `length`.

## Single-Pass with a HashSet
This approach cleverly uses a `HashSet` to count pairs of characters in a single pass through the string. The set is used to keep track of characters that have appeared an odd number of times so far. When a character is encountered that is already in the set, we know we've formed a pair.
**Time:** O(N), where N is the length of the string. We iterate through the string once, and each `HashSet` operation (add, remove, contains) takes O(1) time on average. · **Space:** O(K), where K is the number of unique characters. Since K is at most 52, this is O(1).
**Pros:** Processes the string in a single pass.; The logic is elegant and avoids a second loop over counts.; More efficient than the HashMap approach as it avoids storing full counts.
**Cons:** Still incurs some overhead from hashing, making it slightly less performant than a direct-access array.
### Explanation
This method avoids explicitly counting frequencies and instead focuses on forming pairs directly.

1.  We initialize a `HashSet<Character>` called `oddChars` and an integer `pairs` to 0.
2.  We iterate through the input string `s` character by character.
3.  For each character `c`:
    *   We check if `c` is present in `oddChars`. If it is, we have found a pair. We increment `pairs` by 1 and remove `c` from the set, as it's now part of a pair.
    *   If `c` is not in `oddChars`, it's currently an unpaired character. We add it to the set to wait for its match.
4.  After the loop, `pairs` holds the total number of character pairs. The length contributed by these pairs is `pairs * 2`.
5.  The `oddChars` set now contains all characters that appeared an odd number of times in the string. If the set is not empty, we can use one of these characters as the center of our palindrome, adding 1 to the total length.
6.  The result is `pairs * 2` plus 1 if `oddChars` is not empty.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Set<Character> oddChars = new HashSet<>();
        int pairs = 0;
        for (char c : s.toCharArray()) {
            if (oddChars.contains(c)) {
                pairs++;
                oddChars.remove(c);
            } else {
                oddChars.add(c);
            }
        }
        int length = pairs * 2;
        if (!oddChars.isEmpty()) {
            length++;
        }
        return length;
    }
}
```
### Algorithm
- Initialize a `HashSet<Character>` to keep track of unpaired characters.
- Initialize a variable `pairs = 0` to count the number of character pairs found.
- Iterate through each character `c` of the string `s`.
- If the `HashSet` already contains `c`, it means we've found a matching pair. Increment `pairs` and remove `c` from the set.
- If the `HashSet` does not contain `c`, it's an unpaired character so far. Add `c` to the set.
- After the loop, the total length from pairs is `pairs * 2`.
- If the `HashSet` is not empty, it means there's at least one leftover character that can be the center of the palindrome. Add 1 to the total length.
- Return the final length.

## Using an Array for Frequency Counting
This is the most efficient approach for this problem. Given that the character set is limited to lowercase and uppercase English letters, we can use a simple array as a direct-access map to count character frequencies. This method is faster than using a `HashMap` or `HashSet` because it avoids the overhead of hashing.
**Time:** O(N), where N is the length of the string `s`. The first loop to populate the frequency array is O(N). The second loop to calculate the length runs a fixed number of times (128), making it an O(1) operation. Thus, the total time complexity is dominated by the first loop. · **Space:** O(1), as the `counts` array has a fixed size of 128, which does not depend on the input string's length.
**Pros:** Extremely fast due to direct array indexing, which avoids any hashing overhead.; Minimal space overhead with a small, fixed-size array.; The implementation is simple and concise.
**Cons:** This specific implementation is tailored to the ASCII character set and would need modification for larger character sets like Unicode.
### Explanation
The problem statement guarantees that the input string only contains English letters. This allows us to use a fixed-size array for frequency counting, which is extremely fast.

1.  We declare an integer array `counts` of size 128. This size is sufficient to cover the ASCII values of all uppercase ('A'-'Z') and lowercase ('a'-'z') letters.
2.  We iterate through the input string `s`. For each character `c`, we use its ASCII value as an index into the `counts` array and increment the value at that index (`counts[c]++`).
3.  After counting, we calculate the length of the palindrome. We initialize `length = 0`.
4.  We iterate through the `counts` array. For each `count`, we add `(count / 2) * 2` to `length`. This effectively discards at most one occurrence of each character (if the count is odd) and sums up the rest.
5.  After the loop, `length` holds the maximum possible length from paired characters. If this `length` is smaller than the original string length, it means there was at least one character with an odd count. We can use one of these as a central character, so we add 1 to the `length`.
6.  The final `length` is the answer.

```java
class Solution {
    public int longestPalindrome(String s) {
        int[] counts = new int[128]; // 'z' has ASCII value 122
        for (char c : s.toCharArray()) {
            counts[c]++;
        }

        int length = 0;
        for (int count : counts) {
            length += (count / 2) * 2;
        }

        if (length < s.length()) {
            length++; // Add a single character for the center if there are any leftovers
        }

        return length;
    }
}
```
### Algorithm
- Initialize an integer array `counts` of size 128 to all zeros. This array will map ASCII values to their frequencies.
- Iterate through the input string `s`. For each character `c`, increment the count at its corresponding ASCII index: `counts[c]++`.
- Initialize `length = 0`.
- Iterate through the `counts` array. For each `count`, add `(count / 2) * 2` to `length`. This sums up the contributions of all character pairs.
- After the loop, if the calculated `length` is less than the original string's length (`s.length()`), it implies there was at least one character with an odd count. We can add one such character to the center, so we increment `length` by 1.
- Return `length`.

# Solutions
### Java

```java
class Solution {
public
  int longestPalindrome(String s) {
    int[] cnt = new int[128];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i)];
    }
    int ans = 0;
    for (int v : cnt) {
      ans += v - (v & 1);
      if (ans % 2 == 0 && v % 2 == 1) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestPalindrome(string s) {
    int cnt[128]{};
    for (char &c : s) {
      ++cnt[c];
    }
    int ans = 0;
    for (int v : cnt) {
      ans += v - (v & 1);
      if (ans % 2 == 0 && v % 2 == 1) {
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestPalindrome(self, s: str) -> int: cnt = Counter(s) ans = 0 for v in cnt . values(): ans += v - (v & 1) ans += (ans & 1 ^ 1) and (v & 1) return ans

```