- 难度:
简单
- 本题涉及算法:
哈希表
数组
贪心
- 思路:
哈希表
检查区域
贪心
- 类似题型:
题目 最长回文串
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
示例
输入:"abccccdd"
输出:7
解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
注意:
- 假设字符串的长度不会超过 1010。
解题思路 方法一
- 参考了 拼写单词 构造长度为58的每个元素分别代表一个字母的数组,来简化计算
- 含大小写 长度58,只有大写或小写大小26
- 友情提示:遇到有提示字符串仅包含小写(或者大写)英文字母的题,都可以试着考虑能不能构造长度为26的每个元素分别代表一个字母的数组,来简化计算
代码
public class Solution {
public int longestPalindrome(String s) {
int[] c = new int[58];
for(char cc:s.toCharArray()) {
c[(int)cc-'A']+=1;
}
int res = 0;
boolean flg = false;
for(int i = 0; i<58; i++) {
if(c[i]%2==0&&c[i]!=0){
res+=c[i];
// flg = true;
}
if(c[i]%2==1){
res+=c[i]-1;
flg = true;
}
}
if (flg) {
return res+1;
}else {
return res;
}
}
}
方法二 哈希表
代码
class Solution(object):
def longestPalindrome(self, s):
di = {}
max = 0
for ch in s:
if ch in di:
di[ch] += 1
else:
di[ch] = 1
flag = 0
for d in di:
if di[d]%2==1:
flag = 1
max += di[d]- di[d]%2
else:
max += di[d]
if flag ==1 or len(s)%2==1:
max += 1
else:
return max
return max
方法三:贪心
- 构造长度为58的每个元素分别代表一个字母的数组
代码
public class Solution { public int longestPalindrome(String s) { int[] count = new int[128]; for (char c: s.toCharArray()) count[c]++; int ans = 0; for (int v: count) { ans += v / 2 * 2; if (v % 2 == 1 && ans % 2 == 0) ans++; } return ans; } }
一些高级写法
class Solution:
def longestPalindrome(self, s: str) -> int:
import collections
# 1.统计各字符次数,eg:"ddsad":[3, 1, 1]
count = collections.Counter(s).values()
# 2.统计两两配对的字符总个数,eg: {"ddass":4,"ddsss":4}
x = sum([item//2*2 for item in count if (item//2 > 0)])
# 3.判断是否有没配对的单字符,有结果加一。 eg: {"ddss":4, "ddhjSS":4+1}-->{"ddss":4, "ddhjSS":5}
return x if x == len(s) else x+1
class Solution {
public int longestPalindrome(String s) {
Map<Integer, Integer> count = s.chars().boxed()
.collect(Collectors.toMap(k -> k, v -> 1, Integer::sum));
int ans = count.values().stream().mapToInt(i -> i - (i & 1)).sum();
return ans < s.length() ? ans + 1 : ans;
}
}
错误集
class Solution(object):
def longestPalindrome(self, s):
di = {}
max = 0
for ch in s:
if ch in di:
di[ch] += 1
else:
di[ch] = 1
flag = 0
for d in di:
if di[d]//2> 0: # 忽略了相同字母大于3 输出比预期小1
max += 2 * (di[d]//2)
else:
flag = 1 # 说明有落单的字母
if flag == 1 or len(s)%2==1:
max += 1
else:
return max
return max
class Solution(object):
def longestPalindrome(self, s):
if len(s) <2:
return 1
di = {}
max = 0
for ch in s:
if ch in di:
di[ch] += 1
else:
di[ch] = 1
flag = 0
flag2 = 0
for d in di:
if di[d]//2> 0:
flag = 1
max += 2 * (di[d]//2)
else:
flag2 = 1
if flag ==1 and flag2 == 1 or len(s)%2==1: # 忽略当 s= ab 输出0 预期1
max += 1
else:
return max
return max
class Solution(object):
def longestPalindrome(self, s):
if len(s) <2:
return 1
di = {}
max = 0
for ch in s:
if ch in di:
di[ch] += 1
else:
di[ch] = 1
flag = 0
flag2 = 0
for d in di:
if di[d]//2> 0: # 忽略了 当 s = bbb 4 输出2 预期3
flag = 1
max += 2 * (di[d]//2)
else:
flag2 = 1
if flag ==1 and flag2 == 1:
max += 1
else:
return max
return max
class Solution(object):
def longestPalindrome(self, s):
if len <2:
return 1
di = {}
max = 0
for ch in s:
if ch in di:
di[ch] += 1
else:
di[ch] = 1
flag = 0
flag2 = 0
for d in di:
if di[d]//2> 0:
flag = 1
max += 2 * (di[d]//2)
else:
flag2 = 1
if flag ==1 and flag2 == 1: # 忽略了 当 s=a 时 输出0 预期1
max += 1
else:
return max
return max
PREVIOUS445. 两数相加 II
NEXT365. 水壶问题