algoadvance

Leetcode 409. Longest Palindrome

Problem Statement

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

Example:

Input: s = "abccccdd"

Output: 7

Explanation: One of the longest palindromes that can be built is “dccaccd”, whose length is 7.

Clarifying Questions

  1. Can the input string contain characters other than lowercase or uppercase letters?
    • No, the problem specifies it consists only of lowercase or uppercase letters.
  2. Is the input string guaranteed to have at least one character?
    • Yes, we can assume the input string s is non-empty.
  3. What should be returned if the input string is already a palindrome?
    • Return the length of the input string as it is already a palindrome.

Strategy

To determine the length of the longest palindrome that can be built, follow these steps:

  1. Count Frequency: Use a frequency counter to count occurrences of each character.
  2. Form Palindrome: A palindrome can have at most one character that appears an odd number of times (which would be placed in the middle). The rest should appear an even number of times to ensure symmetry.
  3. Accumulate Length: Sum up the lengths by counting even frequencies directly and adding the largest odd frequencies minus one.
  4. Odd Center Addition: If there are any odd frequencies, add 1 to account for the center character in the palindrome.

This approach ensures that we maximize the length of the palindrome.

Code

Here’s a Java solution implementing the above strategy:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int longestPalindrome(String s) {
        // Step 1: Count the frequency of each character
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // Step 2: Calculate the length of the longest palindrome
        int length = 0;
        boolean oddFrequencyFound = false;

        for (int count : frequencyMap.values()) {
            if (count % 2 == 0) {
                length += count;
            } else {
                length += count - 1; // Add the even part of the count
                oddFrequencyFound = true;
            }
        }

        // Step 3: If any odd frequency was found, add 1 to the length
        if (oddFrequencyFound) {
            length += 1;
        }

        return length;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        String input = "abccccdd";
        int result = sol.longestPalindrome(input);
        System.out.println("The length of the longest palindrome that can be built is: " + result);
    }
}

Time Complexity

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