題目資訊

題目編號: 2131
題目連結: Longest Palindrome by Concatenating Two Letter Words
主題: Array, Hash Table, String, Greedy, Counting

題目敘述

你有一個字串陣列 words。words 的每個元素由兩個小寫英文字母組成。

透過從 words 中選擇一些元素並以任意順序串接它們，來創建最長可能的回文串。每個元素最多可以被選擇一次。

返回你可以創建的最長回文串的長度。如果無法創建任何回文，則返回 0。

回文串是一個正向和反向讀是相同的字串。

範例 1:

輸入: words = ["lc","cl","gg"]
輸出: 6
解釋: 一個最長的回文串是 "lc" + "gg" + "cl" = "lcggcl"，長度為 6。
注意 "clgglc" 是另一個可以創建的最長回文串。

範例 2:

輸入: words = ["ab","ty","yt","lc","cl","ab"]
輸出: 8
解釋: 一個最長的回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt"，長度為 8。
注意 "lcyttycl" 是另一個可以創建的最長回文串。

範例 3:

輸入: words = ["cc","ll","xx"]
輸出: 2
解釋: 一個最長的回文串是 "cc"，長度為 2。
注意 "ll" 是另一個可以創建的最長回文串，也是 "xx"。

約束條件:

$1 \leq \text{words.length} \leq 10^5$
$\text{words}[i].length == 2$
$\text{words}[i]$ 由小寫英文字母組成。

直覺

該問題要求使用給定的兩個字母所組成的單詞數組來構造最長的迴文序列。由於迴文在正向和逆向讀取時相同，因此連接的順序應確保對稱性。關鍵的洞察在於每一個單詞都有可能與其逆序單詞形成一對，以增強迴文的長度。因此，解題方案應系統地識別出這些對。此外，由相同字母構成的單詞（如 “aa”）有可能單獨位於迴文的中心。

解法

此方法採用了系統化的過程來利用頻率數組構造最長的迴文，記錄每一個兩字母單詞及其逆序單詞的出現次數。以下是演算法的結構：

初始化變數：
- 初始化變數 ans 為零，用於追踪正在構建的迴文的總長度。
- 初始化一個大小為 676 的頻率向量（由於存在 26x26 種可能的兩字母組合）為零，用於記錄每一個可能的兩字母組合的出現次數。
索引計算：
- 對於每個單詞，計算一個代表它及其逆序單詞的索引。該索引是基於英文字母中字符的位置計算的，以唯一對應到頻率向量中的位置。
匹配對：
- 對於每一個單詞，通過計算出的索引在頻率數組中查找其逆序單詞是否已存在。
- 如果存在，則意味著可以形成一對，從而為迴文貢獻長度。在這種情況下，將頻率數組中逆序對的位置數減一，並將 ans 增加 4 （因為每一對單詞和它的逆序單詞為迴文長度貢獻了4）。
- 如果沒有找到逆序單詞，就在頻率數組中對其逆序單詞的位置進行遞增。
檢查相同字母對作為中心：
- 在處理完所有單詞後，迴圈檢查頻率數組中是否存在任何由相同字母組成的對（例如 “aa”, “bb”）。
- 如果存在，可以作為迴文的中心元素，從而額外貢獻兩個長度給 ans。
返回結果：
- 最後，返回計算出的長度 ans，這代表了使用給定單詞可以構建的最長迴文。

這種方法確保了時間複雜度為 $O(n)$ 的高效解決方案，其中 $n$ 是單詞的數量，因為它涉及到對單詞進行迴圈和使用索引以及頻率數組進行常數時間的操作。

程式碼

C++

class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        int len = words.size();  // 獲取單詞的數量
        int ans = 0;  // 初始化最長迴文的長度
        vector<short> frequency(676, 0);  // 向量用於統計每對字的出現頻率
        
        for (int i = 0; i < len; i++) {
            // 計算當前單詞及其反向單詞的索引
            int forwardIndex = (words[i][0] - 'a') * 26 + (words[i][1] - 'a');
            int reverseIndex = (words[i][1] - 'a') * 26 + (words[i][0] - 'a');
            
            // 檢查反向對是否存在
            if (frequency[forwardIndex] > 0) {
                frequency[forwardIndex]--;  // 減少正向索引的計數
                ans += 4;  // 迴文長度增加4，因為一對字及其反向增加4的長度
            } else {
                frequency[reverseIndex]++;  // 將當前對字存為反向索引
            }
        }
        
        // 檢查像 "aa" 這樣的對，兩個字符相同
        for (int i = 0; i < 26; i++) {
            if (frequency[27 * i] > 0) {
                ans += 2;  // 結果增加2作為一個中心的單對
                break;  // 只有一個單對可以作為中心使用
            }
        }
        
        return ans;  // 返回可能創建的最長迴文的長度
    }
};

Python

class Solution:
    def longestPalindrome(self, words):
        len_words = len(words)  # 獲取字串陣列的長度
        ans = 0  # 初始化最長回文的長度
        frequency = [0] * 676  # 用來計數每個字對出現頻率的列表
        
        for i in range(len_words):
            # 計算當前字串和其逆序字串的索引
            forwardIndex = (ord(words[i][0]) - ord('a')) * 26 + (ord(words[i][1]) - ord('a'))
            reverseIndex = (ord(words[i][1]) - ord('a')) * 26 + (ord(words[i][0]) - ord('a'))
            
            # 檢查逆序字串是否存在
            if frequency[forwardIndex] > 0:
                frequency[forwardIndex] -= 1  # 減少forwardIndex的計數
                ans += 4  # 增加4到回文的長度，因為字串和其逆序字串使回文長度增加4
            else:
                frequency[reverseIndex] += 1  # 將當前字串儲存為逆序索引
        
        # 檢查是否存在像"aa"這樣的字串，兩個字元均相同
        for i in range(26):
            if frequency[27 * i] > 0:
                ans += 2  # 增加2到結果中，作為單一的中心點
                break  # 只有一對單一字串可作為中心
        
        return ans  # 返回可以構建的最長回文的長度

複雜度分析

時間複雜度: $O(n)$
此演算法的時間複雜度為 $O(n)$，其中 $n$ 為輸入向量 words 的長度。這是因為我們在主迴圈中對 words 向量進行一次迭代，以計算字串對的頻率，這需要 $O(n)$ 的時間。隨後檢查形式為 “aa” 的配對的迴圈迭代了一個固定的次數（26次），這個次數相對於輸入大小是常數，因此不影響整體時間複雜度。
空間複雜度: $O(1)$
此演算法的空間複雜度為 $O(1)$，即常數空間。我們使用了一個固定大小為 676 的向量 frequency（因為有 26 * 26 種可能的小寫字母對），無論輸入 words 的大小如何。frequency 向量所使用的儲存空間不會隨著輸入大小的變化而變化，因此被認為是常數空間複雜度。

CS Note
En

Leetcode 2131. Longest Palindrome by Concatenating Two Letter Words

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析