The naive approach involves exploring every possible path in the graph to count color frequencies. This is typically implemented using Depth First Search (DFS).

1. Start a DFS from every node in the graph.
2. Maintain a frequency map for the current path.
3. Upon extending the path to a neighbor, update the counts and track the maximum value seen so far.
4. Backtrack to explore other branches.
5. To detect cycles, maintain a recursion_stack set. If we encounter a node already in the current recursion stack, a cycle exists.

python
# Pseudo-code for Brute Force
def dfs(node, path_counts):
    path_counts[color[node]] += 1
    max_val = max(path_counts.values())
    
    for neighbor in graph[node]:
        if neighbor in current_path: return -1 # Cycle
        max_val = max(max_val, dfs(neighbor, path_counts))
        
    path_counts[color[node]] -= 1 # Backtrack
    return max_val

Why this fails: The time complexity of this approach is exponential in the worst case. A graph can have an exponential number of paths. For constraints where $N, M \le 10^5$, an $O(N!)$ or even $O(2^N)$ approach will immediately trigger a Time Limit Exceeded (TLE). Furthermore, without memoization, we re-calculate the max color values for the same sub-paths repeatedly.

Core Insight for Largest Color Value in a Directed Graph

The key intuition is to treat the problem as a dynamic programming challenge on a Directed Acyclic Graph (DAG). If we know the maximum frequency of every color for all paths ending at a node $u$, and there is an edge $u \to v$, we can use that information to update the potential maximum frequencies for paths ending at $v$.

However, we cannot simply process nodes in arbitrary order. We must ensure that before we finalize the color counts for node $v$, we have processed all nodes $u$ that have an edge pointing to $v$. This is exactly what Kahn's Algorithm guarantees.

The Invariant: We maintain a DP table dp[node][color], representing the maximum frequency of color in any path ending at node. When traversing from $u \to v$, the transition is: dp[v][color] = max(dp[v][color], dp[u][color]) for all 26 colors.

Once all parents of $v$ have been processed (indicated by $v$'s in-degree dropping to 0), we increment the count for $v$'s own color: dp[v][color_of_v]++.

Visual Description: Imagine the graph as a flow of water. We start at the "source" nodes (in-degree 0). As we "flow" from node $u$ to $v$, we carry the history of color counts with us. Node $v$ acts as a reservoir; it waits until all streams feeding into it (all incoming edges) have delivered their data. Only then does it add its own color contribution and release the flow to its neighbors. If we process $N$ nodes but the reservoir count is less than $N$, water is trapped in a loop (cycle).

Algorithm Strategy: Graph BFS - Topological Sort (Kahn's Algorithm)

1. Graph Construction: Build an adjacency list to represent the graph and an indegree array to store the number of incoming edges for each node.
2. DP State Initialization: Create a 2D array counts[n][26] where counts[i][j] stores the maximum count of the $j$-th lowercase letter in any path ending at node $i$.
3. Queue Initialization: Push all nodes with an indegree of 0 into a queue. These are the starting points of our paths.
4. Process Queue (Kahn's Loop):
   • Dequeue a node $u$.
   • Increment the count corresponding to node $u$'s specific color in counts[u].
   • Update the global maximum answer with counts[u][color_of_u].
   • Iterate through all neighbors $v$ of $u$:
     • For every color $c$ (0 to 25), update $v$'s history: counts[v][c] = max(counts[v][c], counts[u][c]).
     • Decrement indegree[v].
     • If indegree[v] becomes 0, push into the queue.
5. Cycle Detection: Maintain a counter of visited nodes. If the number of visited nodes is less than $n$ after the queue is empty, a cycle exists. Return -1.
6. Result: If no cycle is found, return the global maximum.

Execution Flow

Let's trace the algorithm with colors = "abaca", edges = [[0,1], [0,2], [2,3], [3,4]].

1. Setup:

   • Indegrees: 0:0, 1:1, 2:1, 3:1, 4:1.
   • Queue: [0] (only node 0 has 0 in-degree).
   • counts table initialized to 0s.

2. Process Node 0:

   • Pop 0. Color is 'a'.
   • counts[0]['a'] becomes 1. Max answer = 1.
   • Neighbors: 1 and 2.
   • Update 1: counts[1] inherits counts[0]. indegree[1] becomes 0. Push 1.
   • Update 2: counts[2] inherits counts[0]. indegree[2] becomes 0. Push 2.
   • Nodes visited: 1.

3. Process Node 1:

   • Pop 1. Color is 'b'.
   • counts[1]['b'] becomes 1 (inherited 'a' count is 1). Max answer = 1.
   • No neighbors.
   • Nodes visited: 2.

4. Process Node 2:

   • Pop 2. Color is 'a'.
   • counts[2]['a'] becomes 1 (inherited) + 1 (self) = 2. Max answer = 2.
   • Neighbor: 3.
   • Update 3: counts[3] inherits counts[2]. indegree[3] becomes 0. Push 3.
   • Nodes visited: 3.

5. Process Node 3:

   • Pop 3. Color is 'c'.
   • counts[3]['c'] becomes 1. counts[3]['a'] is 2. Max answer = 2.
   • Neighbor: 4.
   • Update 4: counts[4] inherits counts[3]. indegree[4] becomes 0. Push 4.
   • Nodes visited: 4.

6. Process Node 4:

   • Pop 4. Color is 'a'.
   • counts[4]['a'] becomes 2 (inherited) + 1 (self) = 3. Max answer = 3.
   • No neighbors.
   • Nodes visited: 5.

7. Completion: Visited nodes (5) equals $n$ (5). No cycle. Return 3.

Proof of Correctness

The correctness relies on the properties of Topological Sort and Dynamic Programming:

1. Dependency Resolution: Kahn's algorithm ensures that a node $v$ is processed only after all nodes $u$ pointing to it have been processed. This guarantees that counts[v] has aggregated the maximums from all possible incoming paths before we finalize it.
2. Optimal Substructure: The maximum color value of a path ending at $v$ is determined by the maximum color values of paths ending at its predecessors. By taking the max over all incoming edges, we ensure optimality.
3. Cycle Detection: In a DAG, a topological sort will always visit every node. If the graph has a cycle, the nodes involved in the cycle (and those reachable only from the cycle) will never reach an in-degree of 0 and will never be added to the queue. Comparing the count of processed nodes to $n$ correctly identifies this state.

Reference Implementation

C++ Solution for LeetCode 1857

cpp
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();
        vector<vector<int>> adj(n);
        vector<int> indegree(n, 0);
        
        // Build graph and calculate indegrees
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            indegree[edge[1]]++;
        }
        
        // Initialize Queue with nodes having 0 indegree
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        // dp[i][j] stores max count of color j in a path ending at node i
        vector<vector<int>> dp(n, vector<int>(26, 0));
        
        int nodesSeen = 0;
        int maxColorValue = 0;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            nodesSeen++;
            
            // Process current node's color
            int colorIndex = colors[u] - 'a';
            dp[u][colorIndex]++;
            maxColorValue = max(maxColorValue, dp[u][colorIndex]);
            
            // Propagate counts to neighbors
            for (int v : adj[u]) {
                for (int c = 0; c < 26; c++) {
                    dp[v][c] = max(dp[v][c], dp[u][c]);
                }
                
                indegree[v]--;
                if (indegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        // Cycle detection
        if (nodesSeen < n) return -1;
        
        return maxColorValue;
    }
};

Java Solution for LeetCode 1857

java
import java.util.*;

class Solution {
    public int largestPathValue(String colors, int[][] edges) {
        int n = colors.length();
        List<List<Integer>> adj = new ArrayList<>();
        int[] indegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        
        // Build graph
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            indegree[edge[1]]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }
        
        // dp[i][j] = max count of color j ending at node i
        int[][] dp = new int[n][26];
        int nodesSeen = 0;
        int maxColorValue = 0;
        
        while (!q.isEmpty()) {
            int u = q.poll();
            nodesSeen++;
            
            int uColor = colors.charAt(u) - 'a';
            dp[u][uColor]++;
            maxColorValue = Math.max(maxColorValue, dp[u][uColor]);
            
            for (int v : adj.get(u)) {
                // Propagate max color counts to neighbor
                for (int c = 0; c < 26; c++) {
                    dp[v][c] = Math.max(dp[v][c], dp[u][c]);
                }
                
                indegree[v]--;
                if (indegree[v] == 0) {
                    q.offer(v);
                }
            }
        }
        
        if (nodesSeen < n) return -1; // Cycle detected
        
        return maxColorValue;
    }
}

Python Solution for LeetCode 1857

python
from collections import deque

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        n = len(colors)
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        
        # Build graph
        for u, v in edges:
            adj[u].append(v)
            indegree[v] += 1
            
        # Initialize queue
        queue = deque([i for i in range(n) if indegree[i] == 0])
        
        # dp[i][j] stores max count of color j ending at node i
        dp = [[0] * 26 for _ in range(n)]
        
        nodes_seen = 0
        max_color_value = 0
        
        while queue:
            u = queue.popleft()
            nodes_seen += 1
            
            u_color = ord(colors[u]) - ord('a')
            dp[u][u_color] += 1
            max_color_value = max(max_color_value, dp[u][u_color])
            
            for v in adj[u]:
                # Propagate counts
                for c in range(26):
                    dp[v][c] = max(dp[v][c], dp[u][c])
                
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
                    
        if nodes_seen < n:
            return -1
            
        return max_color_value