LeetCode-409. 最长回文串(Goland实现)

不念不忘少年蓝@ 2022-12-05 15:28 57阅读 0赞

> LeetCode题号：[409. 最长回文串][409.]
> 
> 问题描述：
> 
>        给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
> 
> 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
> 
> 注意:  
> 假设字符串的长度不会超过 1010。

> **示例 1:**
> 
>     输入:
>     "abccccdd"
>     输出:
>     7
>     解释:
>     我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

> 解题思路：
> 
>  1、先定义一个map统计所有字符出现；
> 
>  2、a、如果没有奇数长度串，len = sum（所有偶数长度和）
> 
>        b、如果存在奇数长度串，len = sum（所有偶数长度和）+sum（所有奇数串长度和-1）+1
> 
> 听我分析完，简单吧；上代码，通俗易懂！

func longestPalindrome(s string) int {
    	var m = make(map[string]int)
    	for i := 0; i < len(s); i++ {
    		//统计所有字母出现次数
    		m[string(s[i])]++
    		//_, ok := m[string(s[i])]
    		//if ok {
    		//	m[string(s[i])]++
    		//} else {
    		//	m[string(s[i])] = 1
    		//}
    	}
    	//回文长度
    	var l int = 0
    	//标记是否存在奇数对
    	var flag = false
    	//最长组合，即为，1：存在奇数串，l=所有偶数对长度+（所有奇数串长度-奇数串个数+1）2、不存在奇数串：l=所有偶数对长度
    	for _, v := range m {
    		if len(m) == 1 {
    			return v
    		}
    		if v%2 == 0 {
    			l += v
    		} else {
    			flag = true
    			//奇数串长度变偶数长度
    			l += v - 1
    		}
    	}
    	//只要存在奇数串，则最大奇数串可以放最中间，则不需要做减1 处理
    	if flag {
    		return l + 1
    	}
    	return l
    }

--------------------

### 往期回顾： ###

【1】[LeetCode-122. 买卖股票的最佳时机 II(Goland实现)  ][LeetCode-122. _ II_Goland]

【2】[LeetCode-剑指 Offer 03. 数组中重复的数字(Goland实现)  ][LeetCode-_ Offer 03. _Goland]

【3】[LeetCode-58. 最后一个单词的长度(Goland实现)][LeetCode-58. _Goland]

--------------------

> ❤如果文章对您有所帮助，就在文章的右上角或者文章的末尾点个赞吧！(づ￣ 3￣)づ 
> 
> ❤如果喜欢大白兔分享的文章，就给大白兔点个关注吧！(๑′ᴗ‵๑)づ╭❤～
> 
> ❤对文章有任何问题欢迎小伙伴们下方留言或者入群探讨【群号：708072830】
> 
> ❤鉴于个人经验有限，所有观点及技术研点，如有异议，请直接回复讨论(请勿发表攻击言论)

[409.]: https://leetcode-cn.com/problems/longest-palindrome/
[LeetCode-122. _ II_Goland]: https://blog.csdn.net/weixin_43970743/article/details/108470400
[LeetCode-_ Offer 03. _Goland]: https://blog.csdn.net/weixin_43970743/article/details/108400502
[LeetCode-58. _Goland]: http://https//blog.csdn.net/weixin_43970743/article/details/108377917