Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For each node and each color, keep the greatest count of that color along any path reaching the node. Different colors may use different best paths; that is fine because the objective maximizes one color count. Topological order ensures all incoming paths are considered before a node propagates its counts.

Approach

Build adjacency lists and indegrees, then queue every zero-indegree node. When processing a node, add one to its own color's count and update the global maximum. Propagate coordinate-wise maxima into each neighbor, decrementing its indegree and queuing it once all predecessors are processed. Count processed nodes. Return -1 if that count is below the total, indicating a directed cycle anywhere in the graph; otherwise return the maximum color count.

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)

        adj = defaultdict(list)
        indegree = defaultdict(int)
        for a, b in edges:
            adj[a].append(b)
            indegree[b] += 1

        q = deque([node for node in range(n) if indegree[node] == 0])

        res = 0
        freq = [[0] * 26 for _ in range(n)] # freq[node][color]
        visited = 0

        while q:
            node = q.popleft()
            visited += 1
            curr = ord(colors[node]) - ord('a')
            freq[node][curr] += 1
            res = max(res, max(freq[node]))

            for nei in adj[node]:
                for i in range(26):
                    freq[nei][i] = max(freq[nei][i], freq[node][i])
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)

        return res if visited == n else -1

Complexity analysis

Let n be the number of vertices and e the number of edges. Time: O(n + 26e) for topological processing and propagating 26 color counts across each edge. Auxiliary space: O(e + 26n).