Scale Engineer

Longest Palindrome

Easy
#0396Time: 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).3 companies
Patterns
Greedy
Data structures
Hash TableString
Companies
AkamaiWalmart LabsHP

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.
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;    }}

Complexity

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

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem