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.
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.
My Solution
We first find the count of each character in the string. Then we iterate through all mappings. We are allowed one odd count so if the count is odd and we have used our quota of 1 odd count, we add count-1 to the total. Otherwise we add the full count to the total and return the result after we have processed all mappings.
Time complexity is O(n) to create the counts HashMap as well as to iterate through the counts HashMap. Space complexity is also O(n) to maintain the counts HashMap.
class Solution {
public int longestPalindrome(String s) {
boolean extra = false;
Map<Character,Integer> counts = new HashMap<>();
int out = 0;
for (char c : s.toCharArray()) {
counts.put(c, counts.getOrDefault(c,0)+1);
}
for (char c : counts.keySet()) {
int count = counts.get(c);
if (count % 2 == 1 && !extra) {
out += count;
extra = true;
}
else if (count % 2 == 1) {
out += (count-1);
}
else {
out += count;
}
}
return out;
}
}