https://leetcode.com/problems/longest-palindrome/description/
Problem:
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
|
1 2 3 4 5 6 7 8 |
Input: "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7. |
Idea:
Greedy + Counting
Solution:
C++
|
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 27 |
// Author: Huahua // Time complexity: O(n) // Space complexity: O(128) = O(1) // Running time: 3 ms 9/2017 class Solution { public: int longestPalindrome(const string& s) { vector<int> freqs(128, 0); for (const char c : s) ++freqs[c]; int ans = 0; int odd = 0; for (const int freq : freqs) { // same as: ans += freq % 2 == 0 ? freq : freq - 1; // same as: ans += freq / 2 * 2; // same as: ans += ((freq >> 1) << 1); // same as: ans += freq & (INT_MAX - 1); ans += freq & (~1); // clear the last bit odd |= freq & 1; } ans += odd; return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 11 ms class Solution { public int longestPalindrome(String s) { int[] freqs = new int[128]; for (int i = 0; i < s.length(); ++i) ++freqs[s.charAt(i)]; int ans = 0; int odd = 0; for (int freq: freqs) { ans += freq & (~1); odd |= freq & 1; } return ans + odd; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
""" Author: Huahua Running time: 39 ms """ class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: int """ freqs = [0] * 128 for c in s: freqs[ord(c)] += 1 ans, odd = 0, 0 for freq in freqs: ans += freq & (~1) odd |= freq & 1 return ans + odd |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment