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

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay