2306. Naming a Company

Naming a Company

題目描述： 給定一個字串陣列 ideas，從中選兩個不同的字串，交換它們的首字母後，若兩個新字串都不在原陣列中，則這對是一個有效的公司名稱。求有效配對的總數。

解題思路：

1. 按首字母分組：將所有字串按首字母分成 26 個集合，每個集合存放去掉首字母後的後綴。
2. 對每對首字母 (a, b)（a != b），計算交換後都不衝突的配對數：
   • 後綴同時出現在集合 a 和集合 b 中的不能配對（交換後仍存在於原陣列）。
   • 設集合 a 的大小為 sa，集合 b 的大小為 sb，兩集合的交集大小為 c。
   • 有效配對數 = (sa - c) * (sb - c)。
   • 由於 (a, b) 和 (b, a) 是不同的配對，需乘以 2。
3. 累加所有首字母對的結果。

時間複雜度：O(n * m) — n 為字串數量，m 為平均字串長度。對每對首字母比較交集需遍歷較小集合，總計所有遍歷次數為 O(n)，每次雜湊查詢 O(m)。外層 26*25/2 = 325 對首字母為常數。

空間複雜度：O(n * m) — 儲存所有後綴的雜湊集合。

位元遮罩優化 O(n * 26)：對每個後綴，用 26 位的 bitmask 記錄它出現在哪些首字母分組中。然後對每對 (a, b)，遍歷後綴集合統計交集。在後綴重複率高時更快。

暴力枚舉 O(n^2 * m)：檢查所有字串對，模擬交換首字母並在集合中查找。時間複雜度過高，不可行。

1. 如果允許交換任意位置的字元（不限首字母），問題難度如何變化？
2. 如何優化使得在後綴集合極大時仍高效？（提示：考慮遍歷較小的集合）
3. 如果字串可以重複出現在 ideas 中，需要如何調整算法？