JavaScript 面試必考：查找字符串中出現次數最多的字符及其計數（兩種高效算法）

前言：看似簡單，實則考察數據結構與算法思維

「給定一個隨機字符串，找出出現次數最多的字符及其計數」是前端/全棧面試高頻題。它考察：對象/Map 計頻、遍歷技巧、時間空間複雜度權衡、邊界處理。本文提供兩種經典解法，並延伸至生產級健壯實現。

一、解法一：對象/Map 計頻 + 單次遍歷找最大（標準解，O(n)）

1.1 核心邏輯

1. 遍歷字符串，以字符為 Key，出現次數為 Value 存入對象/Map
2. 遍歷對象/Map，找出 Value 最大的 Key-Value 對

1.2 代碼實現 (ES6+ 推薦)

function findMaxChar(str) {
    if (!str || typeof str !== 'string') return { char: '', count: 0 };

    // 1. 計頻：使用 Map 保持插入順序、支持任意字符 Key
    const freqMap = new Map();
    for (const ch of str) {
        freqMap.set(ch, (freqMap.get(ch) || 0) + 1);
    }

    // 2. 找最大：單次遍歷 Map
    let maxChar = '';
    let maxCount = 0;
    for (const [ch, count] of freqMap) {
        if (count > maxCount) {
            maxCount = count;
            maxChar = ch;
        }
    }

    return { char: maxChar, count: maxCount };
}

// 測試
console.log(findMaxChar("fjalsfj1fds;lafsafafafasfas")); 
// { char: 'a', count: 8 } (假設 a 出現 8 次)
console.log(findMaxChar("adadfdfseffserfefsefseeffffftsdg"));
// { char: 'f', count: 10 } (假設 f 出現 10 次)

1.3 兼容寫法 (ES5 / 面試白板)

function findMaxCharLegacy(str) {
    if (!str) return { char: '', count: 0 };
    var freq = {}; // 普通對象作哈希表
    for (var i = 0; i < str.length; i++) {
        var ch = str.charAt(i);
        freq[ch] = (freq[ch] || 0) + 1;
    }
    var maxChar = '', maxCount = 0;
    for (var ch in freq) {
        if (freq[ch] > maxCount) {
            maxCount = freq[ch];
            maxChar = ch;
        }
    }
    return { char: maxChar, count: maxCount };
}

1.4 複雜度分析

• 時間：O(n) — 遍歷字符串 O(n) + 遍歷 Map O(k) (k ≤ n，不同字符數)
• 空間：O(k) — 存儲不同字符計數

二、解法二：原地替換消除法（空間 O(1)，但破壞原字符串，O(n²) 時間）

2.1 核心邏輯

1. 取字符串首字符 ch
2. 用 replace(new RegExp(ch, 'g'), '') 全局替換移除所有 ch
3. 原長度 - 新長度 = ch 出現次數
4. 重複直到字符串為空，記錄最大計數對應字符

2.2 代碼實現

function findMaxCharReplace(str) {
    if (!str) return { char: '', count: 0 };
    var maxCount = 0, maxChar = '';
    while (str.length > 0) {
        var ch = str.charAt(0);
        var originalLen = str.length;
        // 關鍵：動態構建正則，全局替換
        str = str.replace(new RegExp(ch.replace(/[.*+?^${}()|[\]\\]/g, '\\$&'), 'g'), '');
        var count = originalLen - str.length;
        if (count > maxCount) {
            maxCount = count;
            maxChar = ch;
        }
    }
    return { char: maxChar, count: maxCount };
}

2.3 關鍵細節：正則轉義

ch.replace(/[.*+?^${}()|[\]\\]/g, '\\$&') 必須對特殊字符轉義，否則 .*+?^${}()|[]\ 等會被正則引擎誤解析導致錯誤或安全風險 (ReDoS)。

2.4 複雜度分析

• 時間：O(n²) — 外層循環 O(k)，內層 replace 掃描整個字符串 O(n)，總體 O(k·n) ≈ O(n²)
• 空間：O(1) 額外空間（修改原字符串），但 JS 字符串不可變，實際每次 replace 創建新字符串，空間實為 O(n²)

評價：此解法僅作為面試展示「異常思維」，生產環境嚴禁使用：性能差、正則風險、破壞原數據、無法處理 Unicode 組合字符。

三、生產級健壯增強版（處理並列最大、Unicode、大小寫敏感配置）

/**
 * 查找出現次數最多的字符(支持多個並列最大)
 * @param {string} str 輸入字符串
 * @param {Object} options 配置
 * @param {boolean} options.caseSensitive 是否大小寫敏感，默認 true
 * @param {boolean} options.returnAllMax 是否返回所有並列最大字符，默認 false
 * @returns {Object|Array} {char, count} 或 [{char, count}, ...]
 */
function findMaxCharAdvanced(str, options = {}) {
    const { caseSensitive = true, returnAllMax = false } = options;
    if (!str || typeof str !== 'string') return returnAllMax ? [] : { char: '', count: 0 };

    const processStr = caseSensitive ? str : str.toLowerCase();
    const freqMap = new Map();
    
    // 正確遍歷 Unicode 字符（支持 Emoji、組合字符）
    for (const ch of processStr) {
        freqMap.set(ch, (freqMap.get(ch) || 0) + 1);
    }

    // 找最大計數
    let maxCount = 0;
    for (const count of freqMap.values()) {
        if (count > maxCount) maxCount = count;
    }

    // 收集所有並列最大字符
    const maxChars = [];
    for (const [ch, count] of freqMap) {
        if (count === maxCount) maxChars.push({ char: ch, count });
    }

    return returnAllMax ? maxChars : maxChars[0];
}

// 使用示例
console.log(findMaxCharAdvanced("aabbbcc")); 
// { char: 'b', count: 3 }
console.log(findMaxCharAdvanced("aabbbcc", { returnAllMax: true }));
// [ { char: 'b', count: 3 } ]
console.log(findMaxCharAdvanced("aabbcc", { returnAllMax: true }));
// [ { char: 'a', count: 2 }, { char: 'b', count: 2 }, { char: 'c', count: 2 } ]
console.log(findMaxCharAdvanced("😀😀😃😃😃", { returnAllMax: true }));
// [ { char: '😃', count: 3 } ] (正確處理 Emoji)

四、面試加分點：延伸問題與回答要點

五、總結

面試中遇到此題：

1. 首推解法一：Map 計頻 + 單次遍歷，時間 O(n)、空間 O(k)，代碼清晰、健壯、可擴展。
2. 了解解法二：原地替換消除法，展示發散思維，但明確指出生產不可用並說明缺陷。
3. 主動拓展：Unicode 處理、並列最大返回、大小寫配置、Top K 延伸、大數據流式處理，體現工程深度。

掌握這道題的標準解、優化解、邊界處理、延伸思考，足以應對 90% 以上同類面試考察。