algoadvance

Leetcode 409. Longest Palindrome

Problem Statement

Given a string s which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

Clarifying Questions

  1. Q: Are we allowed to include all characters in the final palindrome?
    • A: Yes, you can use any given characters. However, each character needs to fit the palindrome structure, which means characters that appear an even number of times can be fully used, and one character that appears an odd number of times can be placed in the center.
  2. Q: How do we treat case sensitivity?
    • A: Treat uppercase and lowercase characters as distinct (i.e., “A” and “a” are different characters).
  3. Q: Can the input string be empty?
    • A: Yes, and in that case, the output should be 0.

Strategy

To form the longest palindrome, consider the following steps:

  1. Count Frequency: Count the frequency of each character in the given string using a hash map.
  2. Calculate Length: Traverse through the hash map:
    • If a character has an even frequency, add it to the palindrome length.
    • If a character has an odd frequency, add frequency - 1 to the length (to make it even).
  3. Odd Frequency Center: Finally, if there was any character with an odd frequency, add 1 to the palindrome length (since we can place one odd character in the center).

Code

#include <iostream>
#include <unordered_map>
#include <string>

int longestPalindrome(std::string s) {
    std::unordered_map<char, int> charCount;
    
    // Count the frequency of each character
    for (char ch : s) {
        charCount[ch]++;
    }
    
    int length = 0;
    bool oddIncluded = false;
    
    // Calculate the maximum length of the palindrome
    for (const auto& pair : charCount) {
        if (pair.second % 2 == 0) {
            length += pair.second;
        } else {
            length += pair.second - 1;
            oddIncluded = true;
        }
    }
    
    // Add one for the central odd character if there was an odd count
    if (oddIncluded) {
        length += 1;
    }
    
    return length;
}

int main() {
    std::string input = "abccccdd";
    std::cout << "Length of the longest palindrome: " << longestPalindrome(input) << std::endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s.

This ensures the solution is efficient for large inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI