贪心算法：LeetCode 409 最长回文串双 100 题解

14/Jan/2023 · 2 minute read

这篇文章分享如何借助位的思想将 LeetCode 409——最长回文串的题解优化到双 100。

题目

题目本身是 easy 级别的，原题目是：

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

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

思路分析

基本的思路是遍历字符串中的所有字符，并且统计每个字符出现的次数，最后求和 length：

这个思路的基本原则是所有出现次数为偶数的字符可以刚好位于回文中心的两侧，而最多只能有一个长度为奇数的回文中心，超过的子串就只能舍弃掉一个字符使其变成偶数长度。

对应代码

func longestPalindrome(s string) int {
    stats := map[rune]int{}
    for _, b := range s {
        if _, found := stats[b]; !found {
            stats[b] = 0
        }
        stats[b]++
    }

    length := 0
    hasOdd := false
    for _, count := range stats {
        if count % 2 == 0 {
            length += count
            continue
        }
        if !hasOdd {
            length += count
            hasOdd = true
            continue
        }
        length += (count - 1)
    }
    return length
}

这个题解得到的结果是 100% 时间优势，39% 空间优势，空间占用看来有比较大的优化空间。

优化思路分析

第一遍的算法思路，为了统计，我们用了一个字典来存储各个字符的出现次数，并且需要在统计完成后再一次遍历统计得到的字典。最明显的问题是空间的消耗，每个字符都需要一个 int 类型的数据结构，一般涉及字典以及计数，我都会在优化的时候想一下能不能用位来标记。

因为题目中给定字符串中所有可能的字符均为大小写字母，而参考 ASCII 码中，'A' 的码值为 65，最大码值的 'z' 为 122，相差 57，如果我们用一个 uint64 类型的变量来表示，则刚好可以容纳所有字母的表示，因为 57 < 64。

而改为位标记之后，因为一个位只能表示 0 或者 1，则我们需要考虑一个字符出现次数超过 1 次之后的处理。根据回文的特点，只要一个字符两两出现，则一定可以添加到回文串中，于是我们考虑每次用一个位表示某个字符是否已经出现过，如果是，再遇到一个时，该位置为 0，length 加 2；如果某个字符未曾出现或者之前已经因为偶数置为0，再遇到一个相同字符时，该字符所对应的位置为 1。

算法的整体思路描述：

对应代码：

func longestPalindrome(s string) int {
    var stats uint64
    var length int

    for i := 0; i < len(s); i++ {
        bits := s[i] - 'A'
        if stats >> bits & 1 == 1 {
            length += 2
            stats &= (math.MaxUint64 - 1<<bits)
            continue
        }
        stats |= 1<<bits
    }
    for i := 0; i < 64; i++ {
        if stats >> i & 1 == 1 {
            length++
            break
        }
    }

    return length
}

这个新的思路里，一方面使用一个 uint64 代替了原来的字典，空间复杂度变成 O(0)，另外使用了位操作，逻辑稍微复杂了一点。最终提交结果为双 100。

LeetCode 409 提交结果