左右對稱 Longest Palindrome 最長的回文字串長度 Leetcode #409

Sergiu Vălenaș on Unsplash

題目敘述 Longest Palindrome

給定一個字串s，以s擁有的字元製造回文字串。
請問能製造出的回文字串長度最長是多少？

測試範例

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
'dccaccd', 'cdcacdc','ccdadcc'
或
'dccbccd', 'cdcbcdc','ccdbdcc'
最大長度都是7​

Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

最大長度就是'a'本身，也是回文字串。​

約束條件

Constraints:

• 1 <= s.length <= 2000

字串s的長度介於1~2000之間。

• s consists of lowercase and/or uppercase English letters only.

字串s只會有大寫、小寫英文字母。

觀察

回文字串不外乎兩種模式

對稱部分 + 核心字元 + 對稱部分，其中，核心字元在正中央出現一次。

或者

對稱部分 + 對稱部分

那麼，我們可以推理得知，只要是偶數出現次數的字元，一定可以均勻分布在左右兩側形成對稱部分，進一步構成回文字串。

如果有出現奇數次的字元，就任意挑一個去當核心字元，扣掉核心那次，剛好又變成偶數出現次數，又可以均勻分布在左右兩側形成對稱部分，進一步構成回文字串。

演算法 統計出現次數

承接觀察點的思考。

凡是出現偶數次的字元，一定可以構成回文字串。

凡是出現奇數次的字元，任意挑一個去當核心字元，扣掉核心那次，剛好又變成偶數出現次數，又可以均勻分布在左右兩側形成對稱部分，進一步構成回文字串。

# 表達在這個敘述
(odd_counts > 0) 

其他沒有被挑到的奇數次字元，都各自捨棄一次出現機會，剛好都變成偶數出現次數，又可以均勻分布在左右兩側形成對稱部分，進一步構成回文字串。

# 表達在這個敘述
total_length - odd_counts

程式碼 統計出現次數

class Solution:
    def longestPalindrome(self, s: str) -> int:
        
        total_length = len(s)
        odd_counts = sum(1 for char, occurrence in Counter(s).items() if (occurrence & 1) )
        
        # First, we can choose one character from odds as center of palindrome
        # For example, 'bbabb' or 'bab'.
        
        # If all characters are of even occurrence, then put them on left-hand side and right-hand side evenly.
        # For example, 'bbbffbbb'
        
        # Second, for each characters with odd occurrence, discard one character of its own to make it with even occurrence (therefore they can be palindrome always)
        # For example, 'aaa' -> 'aa', 'ccccc' -> 'cccc'
        
        return (odd_counts > 0) + total_length - odd_counts

複雜度分析

時間複雜度: O(n)

掃描過每個字元，統計出現數，總共耗時O(n)。

空間複雜度: O(26*2) = O(1)

題目已經說只會有大寫、小寫英文字母，那麼字典最多只會占用O(26*2)的空間，為常數級別O(1)。

關鍵知識點

回文字串不外乎兩種模式

對稱部分 + 核心字元 + 對稱部分，其中，核心字元在正中央出現一次。

或者

對稱部分 + 對稱部分

從回文字串模式推理出盡可能充分利用每個字元的回文字串製造方法。

Reference

[1] Longest Palindrome - LeetCode