DEV Community

Cover image for 409. Longest Palindrome
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

409. Longest Palindrome

409. Longest Palindrome

Difficulty: Easy

Topics: Hash Table, String, Greedy

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome1
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.

Solution:

We can use a hash table to count the occurrences of each character. The key insight here is:

  1. Characters that appear an even number of times can fully contribute to the palindrome.
  2. Characters that appear an odd number of times can contribute up to the largest even number that is less than or equal to their count. However, you can use one odd character as the center of the palindrome, so we can add 1 to the final length if there's at least one character with an odd count.

Let's implement this solution in PHP: 409. Longest Palindrome

<?php
/**
 * @param String $s
 * @return Integer
 */
function longestPalindrome($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$solution = new Solution();
echo $solution->longestPalindrome("abccccdd");  // Output: 7
echo $solution->longestPalindrome("a");  // Output: 1
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Character Counting: We use an associative array $charCount to keep track of the number of occurrences of each character in the string.

  2. Calculate the Palindrome Length:

    • We iterate through the count of each character:
      • If the count is even, we add the full count to the palindrome length.
      • If the count is odd, we add the largest even portion ($count - 1) to the palindrome length and mark that we have found an odd count.
    • If there was at least one character with an odd count, we add 1 to the length to account for the middle character of the palindrome.
  3. Edge Cases: The solution handles cases with strings of length 1 and mixed case sensitivity.

This approach ensures an optimal solution with a time complexity of O(n), where n is the length of the string s.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:


  1. Palindrome A palindrome is a string that reads the same forward and backward. 

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more