763. Partition Labels

Medium

Description

給定一個字串 s，將它分割成盡可能多的片段，使得每個字母最多只出現在一個片段中。回傳每個片段的長度列表。

Example:

Input: s = “ababcbacadefegdehijhklij” Output: [9,7,8]

Intuition#

記錄每個字元的最後出現位置，遍歷時維護當前片段的邊界，邊界到達時切割。

先掃描一遍記錄每個字元的最後出現位置 lastIndex
再次遍歷，維護當前片段的右邊界 end = max(end, lastIndex[c])
當 i == end 時，表示當前片段內的所有字元都不會再出現了，可以切割

Approaches#

1: 暴力（合併區間）#

概念: 為每個字元建立 [首次出現, 最後出現] 的區間，然後做區間合併。
時間複雜度: O(n + k log k)，k 為不同字元數
空間複雜度: O(k)

class Solution {
    fun partitionLabels(s: String): List<Int> {
        val first = IntArray(26) { -1 }
        val last = IntArray(26) { -1 }
        for (i in s.indices) {
            val c = s[i] - 'a'
            if (first[c] == -1) first[c] = i
            last[c] = i
        }
        val intervals = mutableListOf<IntArray>()
        for (i in 0 until 26) {
            if (first[i] != -1) intervals.add(intArrayOf(first[i], last[i]))
        }
        intervals.sortBy { it[0] }
        val result = mutableListOf<Int>()
        var start = intervals[0][0]
        var end = intervals[0][1]
        for (i in 1 until intervals.size) {
            if (intervals[i][0] <= end) {
                end = maxOf(end, intervals[i][1])
            } else {
                result.add(end - start + 1)
                start = intervals[i][0]
                end = intervals[i][1]
            }
        }
        result.add(end - start + 1)
        return result
    }
}

⭐2: Greedy（一次遍歷）#

概念: 預處理每個字元的最後位置後，一次遍歷即可完成切割。
時間複雜度: O(n)
空間複雜度: O(1)（26 個字元的陣列為常數）

class Solution {
    fun partitionLabels(s: String): List<Int> {
        val lastIndex = IntArray(26)
        for (i in s.indices) {
            lastIndex[s[i] - 'a'] = i
        }
        val result = mutableListOf<Int>()
        var start = 0
        var end = 0
        for (i in s.indices) {
            end = maxOf(end, lastIndex[s[i] - 'a'])
            if (i == end) {
                result.add(end - start + 1)
                start = i + 1
            }
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 區間邊界擴展 — 動態更新右邊界，到達邊界時做決策
關鍵技巧: 「每個字元的最後出現位置」決定了片段的最小範圍；這個模式也適用於其他「不重疊分割」問題