AlgoPressAppearance
0409-最长回文串
https://leetcode.cn/problems/longest-palindrome
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如"Aa"不能当做一个回文字符串。
注意: 假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
思路:思考错误，是可以重新排序的
中心扩散法 从索引 i 处开始往两边扩展，如果两边的数值都相等，则继续扩展 注意双数和单数
参考代码
csharp
public class Solution {
private int maxExpand(string s, int startIndex, int endIndex){
while(startIndex > 0 && endIndex <s.Length-1){
startIndex--;
endIndex++;
if(s[startIndex] != s[endIndex]){
break;
}
}
return endIndex - startIndex + 1;
}
public int LongestPalindrome(string s) {
int max = 1;
for(int i=0; i<s.Length-1;i++){
int curMax = maxExpand(s,i,i);
max = Math.Max(curMax,max);
if(s[i] == s[i+1]){
curMax = maxExpand(s,i,i+1);
}
max = Math.Max(curMax,max);
}
return max;
}
}
思路2
误解题目的意思了：
因为客户重新排序，所以用字典表缓存所有数值，双数直接使用，单数的可以用一次
参考代码
csharp
public class Solution {
public int LongestPalindrome(string s) {
Dictionary<char,int> dict = new Dictionary<char,int>();
for(int i=0; i<s.Length; i++){
if(dict.ContainsKey(s[i])){
dict[s[i]]++;
}
else{
dict.Add(s[i],1);
}
}
//取出个数
bool usedOdd = false;
int max = 0;
foreach(char key in dict.Keys){
//优化数字部分,双数直接添加,单数取其中的双数，单数本身只能添加一次
max+= (dict[key] / 2) * 2;
if(!usedOdd && dict[key] % 2 == 1){
max+=1;
usedOdd = true;
}
}
return max;
}
}