---

Problem: Longest Palindrome

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

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 1

The idea behind this solution is to use a HashSet to keep track of characters in the string s. For every character in the string:

• If the character is already present in the set, it means we've found a pair for it, so we remove it from the set and increment the pairs count.

• If the character is not in the set, we add it to the set.

After processing all characters in the string, the number of remaining characters in the set will determine if we can use them to form a palindrome. If the set is empty, it means we can use all pairs of characters, resulting in a palindrome with an even length (pairs * 2). Otherwise, we can use all pairs plus one additional character from the set, resulting in a palindrome with an odd length (pairs * 2 + 1).

class Solution {
    public int longestPalindrome(String s) {

        if (s == null || s.isEmpty()) {
            return 0;
        }

        int pairs= 0;

        Set<Character> set = new HashSet<>();

        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
                set.remove(s.charAt(i));
                pairs++;
            } else {
                set.add(s.charAt(i));
            }
        }

        return set.isEmpty() ? pairs * 2 : pairs * 2 + 1;
    }
}

1. Null or Empty Check:

   • The code first checks if the input string s is null or empty. If s is null or empty, the method returns 0 because no palindrome can be constructed from an empty string.

2. Initialization:

   • pairs: This variable keeps track of the number of pairs of characters that can be used to form a palindrome.

   • set: This HashSet is used to store characters from the string s that have been encountered but not paired.

3. Character Counting:

   • The for loop iterates through each character in the string s.

   • If the character is already present in the set (i.e., it has been encountered before), it means we've found a pair for it. So, we remove the character from the set and increment the pairs count.

   • If the character is not in the set, we add it to the set.

4. Final Result:

   • After processing all characters, the method checks if the set is empty. If the set is empty, it means all characters have been paired. Thus, we can form a palindrome of length pairs * 2.

   • If the set is not empty, it means there are characters that can be used to form a palindrome along with the already paired characters. Thus, we can form a palindrome of length pairs * 2 + 1 such that we can use all pairs plus one additional character from the set in the middle of the palindrome.

Complexities

Time Complexity: O(n)

1. Iterating over the String:

   • The for-loop iterates over the entire string s of length n. This results in a time complexity of O(n).

2. HashSet Operations:

   • Checking if a character is in the set (set.contains()) and removing it (set.remove()) both have an average time complexity of O(1) for a HashSet in Java. This is because hash-based data structures provide constant-time average complexity for these operations.

   • Adding a character to the set (set.add()) also has an average time complexity of O(1).

Therefore, the overall time complexity of the code is dominated by the iteration over the string, which is O(n).

Space Complexity: O(n)

1. HashSet:

   • The HashSet set can store up to n distinct characters from the string s. In the worst-case scenario, all characters in s are unique, and the HashSet will contain n elements.

2. Pairs Variable:

   • The variable pairs is an integer variable that requires a constant amount of space, which can be considered O(1).

Therefore, the overall space complexity of the code is dominated by the HashSet set, which is O(n).

---

Solution 2

class Solution {
    public int longestPalindrome(String s) {

        if (s == null || s.isEmpty()) {
            return 0;
        }

        int[] charFreq = new int[58];

        for (int i = 0; i < s.length(); i++) {
            charFreq[s.charAt(i) - 'A']++;
        }

        int maxLength = 0;

        for (int i = 0; i < 58; i++) {
            maxLength += charFreq[i] / 2 * 2;
        }

        return s.length() > maxLength ? maxLength + 1 : maxLength;
    }
}

1. Null or Empty Check:

   • The code first checks if the input string s is null or empty. If s is null or empty, the method returns 0 because no palindrome can be constructed from an empty string.

2. Frequency Array:

   • An integer array charFreq of size 58 is created. The size 58 is chosen because the given constraint suggests that the input string contains only uppercase and lowercase English letters. Since there are 26 uppercase letters, 26 lowercase letters, and 6 other characters (which are between 'A' and 'a'), we have a total of 58 characters. (Reference: ASCII Table)

3. Counting Character Frequencies:

   • This first for loop iterates through each character in the string s.

   • For each character, its frequency is incremented in the charFreq array. The expression s.charAt(i) - 'A' converts the character into an index of the array, effectively mapping each letter to its position in the array.

4. Calculating Maximum Length of Palindrome:

   • An integer variable maxLength is initialized to 0 to keep track of the maximum length of the palindrome that can be formed from the characters in the string s.

   • The second for loop iterates through the charFreq array.

   • For each character frequency, it calculates the maximum number of characters that can be used in the palindrome. This is done by dividing the frequency by 2 and then multiplying the result by 2 to get the largest even number less than or equal to the frequency. The maximum length of the palindrome is then updated accordingly. This ensures that only complete pairs of characters (which can form palindromes) are added to the length.

5. Adjusting Length for Odd Frequencies:

   • After processing all characters, the method compares the length of the input string s with maxLength to determine the final result.

   • If the length of s is greater than maxLength, it means that there are characters in s that can be used in the middle of the palindrome. Therefore, the method returns maxLength + 1.

   • Otherwise, it returns maxLength as the length of the longest palindrome that can be formed from s.

Complexities

Time Complexity: O(n)

1. Iterative Traversal:

   • The first and second for loops iterate through the characters of the string s and the charFreq array, respectively. In the worst-case scenario, these loops will iterate n and 58 times, respectively, where n is the length of the string s.

   • Thus, the time complexity of the for loops is O(n+58), which is equivalent to O(n) since constants are dropped in Big O notation.

Combining these factors, the overall time complexity of the longestPalindrome method is O(n).

Space Complexity: O(1)

1. Character Frequency Array:

   • The space complexity is primarily due to the integer array charFreq of size 58. The size of the array is constant and does not depend on the length of the input string s. Therefore, the space complexity of the array is O(1).

2. Other Variables:

   • The input string s, the integer variable maxLength, and the loop counters require constant space regardless of the input size.

Thus, the space complexity of the longestPalindrome method is O(1) or constant space.