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

Example 3:

1
2

Input: s = "bb"
Output: 2

Constraints

  • 1 <= s.length <= 2000
  • s consists of lowercase and/or uppercase English letters only.

Solution

Method 1 - Using Hashset

We know that palindrome can be even length or odd length. For even length, we can all the frequency of chars are even. For odd length, we central char with freq odd, but rest of the chars have frequency even.

  • We can add chars to hashset.
  • When we see the char for 2nd time, we will remove it from the set.
  • In the end only odd frequencies will remain in hashset

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {

	public int longestPalindrome(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}

		Set<Character> hs = new HashSet<Character>();
		int count = 0;

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

		if (!hs.isEmpty()) {
			return count * 2 + 1;
		}

		return count * 2;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {

	public int longestPalindrome(String s) {
		Set<Character> set = new HashSet<>();
		int n = s.length();
		for (int i = 0; i < n; i++) {
			if (!set.add(s.charAt(i))) {
				set.remove(s.charAt(i));
			}
		}

		return set.size() <= 1 ? n : n - set.size() + 1;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)