leetcode409：最长回文串（longest-palindrome）

[carloscn]

问题描述

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

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

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

示例 2: 输入:s = "a" 输入:1

示例 3： 输入:s = "aaaaaccc" 输入:7 提示:

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/longest-palindrome

[carloscn]

问题分析

排序后判断：

static int32_t longest_palindrome(char *in_str, size_t *o_len)
{
    int32_t ret = 0;
    size_t i = 0, j = 0, in_len = 0;
    size_t count_no_repeat = 0;
    size_t count_repeat = 0;
    char *buffer = NULL;

    UTILS_CHECK_PTR(in_str);
    UTILS_CHECK_PTR(o_len);
    UTILS_CHECK_LEN(in_len = strlen(in_str));

    if (in_len == 1) {
        *o_len = 1;
        goto finish;
    }

    buffer = (char *)calloc(1, in_len);
    UTILS_CHECK_PTR(buffer);

    memcpy(buffer, in_str, in_len);
    // sort in_str
    ret = utils_sort_char_array(buffer, in_len, ORDER_BY_ASCEND);
    UTILS_CHECK_RET(ret);

    while (i < in_len) {
        if (buffer[i] != buffer[i + 1]) {
            count_no_repeat ++;
            i += 1;
        } else {
            count_repeat += 2;
            i += 2;
        }
    }
    if (count_no_repeat != 0) {
        count_repeat ++;
    }

    *o_len = count_repeat;
finish:
    if (buffer != NULL) {
        free(buffer);
    }
    return ret;
}

[carloscn]

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/str/25_longest-palindrome_409.c

result: