Java 字串去重與壓縮演算法實作：面試高頻題目完整解析

題目背景

兩道經典字串處理面試題：去重 保留首次出現順序，壓縮 連續重複字元編碼為「次數+字元」。限定輸入為小寫字母 a-z，需實作 C 風格函式簽名，對應 Java 陣列操作。

題目一：字串去重

規則：出現重複字元，僅保留第一次出現，其餘濾除。
範例："abacacde" → "abcde"、"deefd" → "def"、"afafafaf" → "af"

Java 實作

/**
 * 字串去重：保留首次出現順序
 * @param input 輸入字元陣列
 * @param len   有效長度
 * @param output 輸出緩衝區（呼叫端預分配，長度 >= len）
 */
static void stringFilter(char[] input, long len, char[] output) {
    boolean[] seen = new boolean[26]; // a-z
    int outIdx = 0;

    for (int i = 0; i < len; i++) {
        int idx = input[i] - 'a';
        if (!seen[idx]) {
            seen[idx] = true;
            output[outIdx++] = input[i];
        }
    }
    // 其餘位置可不處理，呼叫端依 outIdx 判斷有效長度
}

題目二：字串壓縮（Run-Length Encoding 變體）

規則：僅壓縮連續重複字元，格式為 次數+字元；次數為 1 時省略次數。
範例："xxxyyyyyyz" → "3x6yz"、"abcbc" → "abcbc"、"cccddecc" → "3c2de2c"

Java 實作

/**
 * 字串壓縮：連續重複編碼為 次數+字元
 * @param input 輸入字元陣列
 * @param len   有效長度
 * @param output 輸出緩衝區（呼叫端預分配，建議 2*len）
 */
static void stringZip(char[] input, long len, char[] output) {
    if (len == 0) return;

    char prev = input[0];
    int count = 1;
    int outIdx = 0;

    for (int i = 1; i < len; i++) {
        if (input[i] == prev) {
            count++;
        } else {
            // 輸出前一組
            if (count > 1) {
                output[outIdx++] = (char) ('0' + count); // 單位數；超過 9 需多位數處理
            }
            output[outIdx++] = prev;
            prev = input[i];
            count = 1;
        }
    }
    // 處理最後一組
    if (count > 1) output[outIdx++] = (char) ('0' + count);
    output[outIdx++] = prev;
}

完整測試主程式

public class StringAlgorithmTest {
    public static void main(String[] args) {
        char[] test = {'a','a','a','c','b','b','b','a','a','c','a','d','d','d','c','d','e'};
        long len = test.length;

        // 去重測試
        char[] filterOut = new char[(int) len];
        stringFilter(test, len, filterOut);
        System.out.print("去重結果: ");
        for (char c : filterOut) if (c != 0) System.out.print(c);
        System.out.println();

        // 壓縮測試
        char[] zipOut = new char[(int) (2 * len)];
        stringZip(test, len, zipOut);
        System.out.print("壓縮結果: ");
        for (char c : zipOut) if (c != 0) System.out.print(c);
        System.out.println();
    }

    // 將上述 stringFilter、stringZip 方法放在此處
}

演算法複雜度分析

擴展與注意事項

• 計數超過 9：實務中連續字元可能超過 9，需將計數轉為字串逐字元寫入（如 String.valueOf(count)）。
• Unicode 支援：若輸入非 ASCII，seen 陣列需改用 Set<Character> 或位圖。
• 原地修改：若允許原地修改輸入陣列，可節省輸出緩衝區，但需小心覆蓋未讀資料。
• 串流處理：超大資料可改為 Reader/Writer 串流式處理，不載入全文。