2022/06/27

Leetcode Note: Go - Longest Palindrome

Longest Palindrome - LeetCode
https://leetcode.com/problems/longest-palindrome/

Go 言語で取り組んだメモ

所感

string s が渡されるので、渡された文字列で作成可能な最長の回分文字数を int で return する
例: s = abccccdd なら dccaccd が最長回文であり文字数は 7 なので 7 を return する

回答

Longest Palindrome - LeetCode
https://leetcode.com/problems/longest-palindrome/solution/

func longestPalindrome(s string) int {
	count := [128]int{}
	for _, v := range s {
		count[v]++
	}

	answer := 0
	for _, v := range count {
		answer += v / 2 * 2
		if answer%2 == 0 && v%2 == 1 {
			answer++
		}
	}
	return answer
}

count 配列で文字が何度登場したのかをカウント
count 配列をループ
- answer += v / 2 * 2 でパートナーになれる可能性がある数値を産出
  - “aaaaa” という文字列があれば 5 / 2 * 2 = 4 で 4 文字がパートナーにとして成立する可能性がある
- if answer%2 == 0 && v%2 == 1
  - v%2 == 1 はセンター文字列の候補チェック
  - answer%2 == 0 はセンター文字列を既に追加していないかチェック
    - センター文字列を answer に追加していれば answer は常に奇数になるため