Category: Easy
Problem
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.
Examples
Example 1:
1 2 3 4 | Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7. |
Example 2:
1 2 | Input: s = "a" Output: 1 |
Constraints
1 <= s.length <= 2000sconsists of lowercase and/or uppercase English letters only.
Solution Approach
In this problem of the Longest palindrome, we have to find the length of the longest palindrome which can be made from the string that is provided. We need to only return the length and not the string that can be constructed.
To solve the problem we have to look at some inputs to gain the intuition and the pattern hidden in the problem. Every letter in the string can be repeated an even or an odd number of times.
Even odd cases
If any character is repeated even number of times then there is no problem as we can divide and add half of the characters at the beginning and half at the end. To give an example of the same case suppose we have aabb as input then abba can be constructed which will be a valid palindrome.
Now in case, we have characters that are repeated an odd number of times then we can use one of those characters in the middle of the final palindromic string. For example, if we have abb then we can have bab as our answer. To add to the example if suppose we have 2 or more characters that are repeated an odd number of times we have to add one of them as the middle character. For example, for the input aaabbb we can convert it to abba which is a palindrome.
So from the above examples, we have a rough idea that we are only concerned about the frequency of the characters which will make up the string. We can use something like a hashmap or dictionary data structure to store these mappings. Then we have to iterate through the keys in this map and if they have even values then we add that to the result directly. If they have odd values we add the value-1 to the result. In the end, we add one of the odd characters (if any) to the result and return that as the answer.
Complexities
We are passing through the string once and then we are passing through the map once so the time complexity of this approach is O(n). Secondly, we are using the map to store the values so the space complexity of the approach is O(n).
Code Overview
Coming to the code of this approach, we first declare a hashmap and a result variable. This variable will be used to store the result which we will be returning at the end. Next, we add all the characters to the hashmap with the key being the character and value being the frequency. Now we iterate through the map and add the even values of the map to the result. After adding the even value we have to remove that key from the result. If we find any odd value then we add that value – 1 to the result. At the end, we will just add 1 if there is any key left in our hashmap.
Solution code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public int longestPalindrome(String s) { if (s.length() <= 1) return s.length(); HashMap<Character, Integer> map = new HashMap<>(); for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } int res = 0; Iterator<Map.Entry<Character, Integer>> iter = map.entrySet().iterator(); while (iter.hasNext()) { Map.Entry<Character, Integer> next = iter.next(); if (next.getValue() % 2 == 0) { res += next.getValue(); iter.remove(); } else { res += next.getValue() - 1; } } return map.isEmpty() ? res : res + 1; } } |
For more Leetcode explained solutions visit Leetcode Solutions.
If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in the comment section. You can also contact me via the Contact page I will surely respond. Happy Leetcoding 🙂