Is Longest Palindrome easy or hard?

Longest Palindrome is classified as an easy problem. The main challenge is recognizing that palindrome construction depends on character pairs and that only one odd-frequency character can be placed in the center.

How to solve Longest Palindrome in O(n)?

Iterate through the string and track character frequencies using a hash map or set. Each pair of identical characters contributes two characters to the palindrome length. After counting, add all even contributions and allow one odd character to serve as the center, giving a total O(n) runtime.

What is the best approach for Longest Palindrome?

The best approach uses frequency counting with a hash table. Count how many times each character appears, then add all even counts and use at most one odd character as the center. This solution runs in O(n) time and O(k) space, where k is the number of unique characters.

What data structure is used in Longest Palindrome?

A hash table is the primary data structure used to store character frequencies. Some solutions use a set to track characters with odd counts. Both structures rely on constant-time lookups and updates.

What is the time complexity of Longest Palindrome?

The optimal time complexity is O(n), where n is the length of the string. The algorithm scans the string once to count characters and computes the palindrome length from those counts. Space complexity is O(k) for the character frequency map or set.

Longest Palindrome Python or Java solution approach?

Python and Java implementations typically use a dictionary or HashMap to count character frequencies. After counting, iterate through the map, add even values directly, and allow one odd character for the center. The algorithm runs in O(n) time in both languages.

Is Longest Palindrome asked at Google, Amazon, or Meta?

Longest Palindrome is a common easy-level interview problem that appears in screening rounds at companies like Amazon and Meta. It tests understanding of character frequency counting, greedy pairing logic, and basic hash table usage.

Description Solution Video 9:18

409. Longest Palindrome

Easy55.9% acceptance8 companies

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.

Asked at 8 companies

Ubisoft HP Bloomberg

Google Amazon Microsoft Meta

TCS

Topics

9:18

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

409. Longest Palindrome

Asked at 8 companies

Topics

Similar problems