LeetCode 409. 最长回文串

Categories:

题目描述
思路分析
1. 解法一：计数统计（推荐）
相似题目

题目描述

✅ 409. 最长回文串

思路分析

解法一：计数统计（推荐）

核心思路：

统计每个字符的出现次数。

偶数部分全部可以放入回文两侧。

若存在奇数次数字符，可放一个在中心。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，字符集大小为常数。

class Solution {
    public int longestPalindrome(String s) {
        int[] cnt = new int[128];
        for (char c : s.toCharArray()) {
            cnt[c]++;
        }

        int len = 0;
        boolean hasOdd = false;

        // 统计偶数部分与是否存在奇数
        for (int c : cnt) {
            len += (c / 2) * 2;
            if ((c & 1) == 1) {
                hasOdd = true;
            }
        }

        return hasOdd ? len + 1 : len;
    }
}

func longestPalindrome(s string) int {
	cnt := make([]int, 128)
	for i := 0; i < len(s); i++ {
		cnt[s[i]]++
	}

	length := 0
	hasOdd := false

	// 统计偶数部分与是否存在奇数
	for _, c := range cnt {
		length += (c / 2) * 2
		if c%2 == 1 {
			hasOdd = true
		}
	}

	if hasOdd {
		return length + 1
	}
	return length
}

相似题目

题目	难度	考察点
5. 最长回文子串	中等	中心扩展
9. 回文数	简单	回文判断
125. 验证回文串	简单	双指针
680. 验证回文串 II	简单	双指针
516. 最长回文子序列	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/65333411