Longest Palindrome
- 1 min read
- String
- LC-Easy
3 years ago
Solution
- Make counter of each character
- If a character's frequency (let's call this
count), is divisible by 2, add it toans - If it's not, then add
count - 1to the answer, while also keeping track that there is a character with an odd frequency - We can only add one odd length character count to the palindrome, however, we can reduce the count by 1 to make it divisible by 2 and add it immediately.
- At the end, check if our flag is true. If yes, then increment by 1 since there was a character with an odd frequency and we can add one instance of it to our answer
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) | Space is constant because of limited character set |
def longestPalindrome(self, s: str) -> int:
counts = Counter(s)
ans = 0
odd = False
for ch in counts:
count = counts[ch]
if count % 2 == 0:
ans += count
else:
odd = True
ans += count - 1
if odd:
ans += 1
return ans