每日一题-20240206

发表于 更新于 分类于 阅读次数： 本文字数： 301 阅读时长 ≈ 1 分钟

题目描述

409. 最长回文串

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

1
2
3
4
输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

1
2
输入:s = "a"
输出:1

示例 3：

1
2
输入:s = "aaaaaccc"
输出:7

提示:

  • 1 <= s.length <= 2000
  • s 只由小写 和/或 大写英文字母组成

解题思路

在一个回文串中，只有最多一个字符出现了奇数次，其余的字符都出现偶数次

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution409 {
    /**
     * 思路
     * 在一个回文串中，只有最多一个字符出现了奇数次，其余的字符都出现偶数次
     *
     * @param s
     * @return int
     * @author Forest Dong
     * @date 2024/03/04 19:42
     */
    public static int longestPalindrome(String s) {
        int[] count = new int[128];
        int length = s.length();
        for (int i = 0; i < length; ++i) {
            char c = s.charAt(i);
            count[c]++;
        }

        int ans = 0;
        for (int v : count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        String str = "abc1123";
        System.err.println(longestPalindrome(str));
    }
}