2405. Optimal Partition of String

Medium
Description

給定字串 s，將其分割成最少的子字串，使每個子字串中的字元都不重複。回傳最少的分割數量。

Example:

Input: s = “abacaba” Output: 4 （“ab”, “ac”, “ab”, “a”）

Intuition#

核心思路：Greedy——盡可能讓每個子字串最長（包含最多不重複字元）。遇到重複字元時就開始新的子字串。

  • 使用 HashSet 追蹤當前子字串的字元
  • 遇到已存在的字元 -> 計數+1，清空 Set，開始新子字串
  • Greedy 正確性：讓每段盡量長不會讓後面的分割更差

Approaches#

1: HashSet Greedy#

  • 概念: 用 HashSet 記錄當前子字串的字元，遇到重複就清空並計數
  • 時間複雜度: O(n) - 一次遍歷
  • 空間複雜度: O(26) = O(1) - 最多 26 個字母
class Solution {
    fun partitionString(s: String): Int {
        val seen = HashSet<Char>()
        var count = 1

        for (c in s) {
            if (c in seen) {
                count++
                seen.clear()
            }
            seen.add(c)
        }

        return count
    }
}

⭐2: Bitmask Greedy#

  • 概念: 用 26-bit 整數取代 HashSet，每個 bit 代表一個字母是否出現過
  • 時間複雜度: O(n) - 一次遍歷
  • 空間複雜度: O(1) - 一個整數
class Solution {
    fun partitionString(s: String): Int {
        var mask = 0
        var count = 1

        for (c in s) {
            val bit = 1 shl (c - 'a')
            if (mask and bit != 0) {
                count++
                mask = 0
            }
            mask = mask or bit
        }

        return count
    }
}

初始化 count = 1 而非 0，因為即使沒有重複，字串本身就是一個子字串。最後一段子字串不會觸發 count++，所以初始值要從 1 開始。

🔑 Takeaways#

  • Pattern: 最少分割使每段無重複 -> Greedy 最長延伸
  • 關鍵技巧: Bitmask 取代 HashSet 在小字母表場景下更高效；Greedy 的正確性來自於「當前段越長，後面的壓力不會更大」