1857. Largest Color Value in a Directed Graph

Hard
Description

給定一個有向圖，每個節點有一個顏色（小寫字母）。找出所有路徑中，單一顏色出現最多次的數量。若圖有環，回傳 -1。

Example:

Input: colors = “abaca”, edges = [[0,1],[0,2],[2,3],[3,4]] Output: 3

Intuition#

拓撲排序 + DP，每個節點維護從起點到它的路徑上每種顏色的最大出現次數。

  • 若有環則無限循環，回傳 -1
  • 用拓撲排序保證處理順序
  • 每個節點記錄 26 種顏色各自在到達該節點的所有路徑中出現的最大次數

Approaches#

⭐1: 拓撲排序 + DP#

  • 概念: 用 Kahn 演算法做拓撲排序，同時用 DP 陣列追蹤每種顏色的最大出現次數
  • 時間複雜度: O((V + E) * 26)
  • 空間複雜度: O(V * 26)
class Solution {
    fun largestPathValue(colors: String, edges: Array<IntArray>): Int {
        val n = colors.length
        val graph = Array(n) { mutableListOf<Int>() }
        val inDeg = IntArray(n)

        for ((u, v) in edges) {
            graph[u].add(v)
            inDeg[v]++
        }

        // dp[node][color] = 到達 node 的路徑中 color 的最大出現次數
        val dp = Array(n) { IntArray(26) }
        val queue = ArrayDeque<Int>()

        for (i in 0 until n) {
            if (inDeg[i] == 0) queue.add(i)
        }

        var processed = 0
        var result = 0

        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            processed++
            dp[node][colors[node] - 'a']++
            result = maxOf(result, dp[node][colors[node] - 'a'])

            for (next in graph[node]) {
                for (c in 0 until 26) {
                    dp[next][c] = maxOf(dp[next][c], dp[node][c])
                }
                inDeg[next]--
                if (inDeg[next] == 0) queue.add(next)
            }
        }

        return if (processed == n) result else -1
    }
}

2: DFS + 記憶化#

  • 概念: DFS 後序遍歷，用三色標記偵測環，同時計算每個節點的顏色計數
  • 時間複雜度: O((V + E) * 26)
  • 空間複雜度: O(V * 26)
class Solution {
    fun largestPathValue(colors: String, edges: Array<IntArray>): Int {
        val n = colors.length
        val graph = Array(n) { mutableListOf<Int>() }
        for ((u, v) in edges) graph[u].add(v)

        val dp = Array(n) { IntArray(26) { -1 } }
        val state = IntArray(n) // 0: 未訪問, 1: 處理中, 2: 完成
        var result = 0

        fun dfs(node: Int): Boolean {
            if (state[node] == 1) return false // 環
            if (state[node] == 2) return true
            state[node] = 1
            dp[node] = IntArray(26)

            for (next in graph[node]) {
                if (!dfs(next)) return false
                for (c in 0 until 26) {
                    dp[node][c] = maxOf(dp[node][c], dp[next][c])
                }
            }

            dp[node][colors[node] - 'a']++
            result = maxOf(result, dp[node][colors[node] - 'a'])
            state[node] = 2
            return true
        }

        for (i in 0 until n) {
            if (state[i] == 0 && !dfs(i)) return -1
        }
        return result
    }
}

🔑 Takeaways#

  • Pattern: DAG 上的 DP – 拓撲排序確保處理順序，DP 傳遞最優值
  • 關鍵技巧: 每個節點維護 26 種顏色的計數；拓撲排序同時偵測環（processed != n）；在加入自身顏色前先傳遞前驅的資訊