> For the complete documentation index, see [llms.txt](https://grind75-notes.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://grind75-notes.gitbook.io/notes/week-2/longest-palindrome.md).

# Longest Palindrome

{% embed url="<https://leetcode.com/problems/longest-palindrome>" %}

### 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 here.
>
> &#x20;
>
> **Example 1:**
>
> <pre data-overflow="wrap"><code>Input: s = "abccccdd"
> <strong>Output: 7
> </strong><strong>Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
> </strong></code></pre>
>
> **Example 2:**
>
> <pre data-overflow="wrap"><code>Input: s = "a"
> <strong>Output: 1
> </strong><strong>Explanation: The longest palindrome that can be built is "a", whose length is 1.
> </strong></code></pre>

### Pseudocode

{% code overflow="wrap" %}

```
// define what constitues a palindrom
// even length palindrome, all letters have even pairs
// odd length palindrome, one letter is odd 1, 3, 5.. the others must be even
// add letters from string into a map, to build longest palindrome, take all even numbered letters and add the longest odd letter if available 
// omit 1 character from odd length and it becomes even

```

{% endcode %}

### Solution

```javascript
var longestPalindrome = function(s) {

    const map = new Map()
    let evenSum = 0;
    let largestOdd = 0;
    let largestOddLetter = null;

    for (let i = 0; i < s.length; i++) {
        map.set(s[i], map.get(s[i]) + 1 || 1);
    }

    // first pass to add up all the even numbers and obtain largestOdd
    for(const [k, v] of map) {
        if(v % 2 === 0) {
            evenSum += v;
        } else {
            if(v > largestOdd) {
                largestOdd = v;
                largestOddLetter = k;
            } 
        }
    }

    // second pass to add up all the odd numbers - 1 as even excluding largestOdd
    for (const [k, v] of map) {
        if(v % 2 !== 0 && k !== largestOddLetter) {
            evenSum += v - 1;
        }
    }

    return (evenSum + largestOdd);
};


```

### Time and Space Complexity

#### Time

* performed 3 loops independently, first to map the letters, second to obtain sum of even numbers and largest odd, third loop to obtain sum of odd - 1 letters excluding largest odd. O(3N) -> O(N)
* Total - O(N)

#### Space

* stored map of string - O(N)
* Total - O(N)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://grind75-notes.gitbook.io/notes/week-2/longest-palindrome.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.