本文主要是介绍409. Longest Palindrome(最长回文串),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述
给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。
在构造过程中,请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。
问题分析
如果一个串是回文串,那么中间有一个对称轴左边的每一个字符在右边都有对应的字符,所以回文串中除了对称轴的字符可以为奇数外其余字符都为偶数。因此此问题转换为了将其中最大的奇数保留,偶数保留,其余奇数减去一转化为大于等于0的偶数,然后将所有数求和就行了。
代码
int longestPalindrome(char *s){int a[256] = {0};for(int i=0; s[i]!='\0'; i++){a[s[i]]++;}int odd = 0;int length = 0;for(int i=0; i<256; i++){if(a[i]&1){if(odd!=0){if(odd<a[i]){length += odd - 1;odd = a[i];}else{length += a[i] - 1;}}else{odd = a[i];}}else{length += a[i];}}return length+odd;
}
提交结果截图
这篇关于409. Longest Palindrome(最长回文串)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!