字串去重演算法：四種經典解法與效能分析

問題定義

給定一字串，移除其中重複字元，保留首次出現順序。例如 "zayyyy" → "zay"。

四大解法詳解

方法一：暴力雙迴圈（Brute Force）

• 思路：外層遍歷每字元，內層檢查前方是否已出現。
• 複雜度：時間 O(n²)、空間 O(1)。
• 適用：極短字串、教學示範。

方法二：排序後比較

• 思路：將字串轉字元陣列排序，相鄰比較去重。
• 缺點：破壞原始順序，需額外記錄原索引才能還原，實務較少用。
• 複雜度：時間 O(n log n)、空間 O(n)。

方法三：位元陣列 / 空間換時間（Bit Vector）

• 思路：ASCII 僅 256 字元，用 256 bits（8 個 int32）記錄出現狀態。
• 複雜度：時間 O(n)、空間 O(1)（固定 256 bits）。
• 代碼實現（Java）：

  public static String removeDuplicate(String str) {
      char[] chars = str.toCharArray();
      int[] flags = new int[8]; // 8 * 32 = 256 bits
      int len = chars.length;
  
      for (int i = 0; i < len; i++) {
          int idx = chars[i] / 32;
          int shift = chars[i] % 32;
          if ((flags[idx] & (1 << shift)) != 0) {
              chars[i] = '\0'; // 標記重複
          }
          flags[idx] |= (1 << shift);
      }
  
      // 壓縮結果
      int j = 0;
      for (int i = 0; i < len; i++) {
          if (chars[i] != '\0') chars[j++] = chars[i];
      }
      return new String(chars, 0, j);
  }