Largest color value in a directed graph

Hash Table String Dynamic Programming Graph Theory Topological Sort Memoization Counting

57.3% acceptance

Feb 25, 2026

2614

There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1. You are given a string colors where colors[i] is a lowercase English letter representing the color of the ith node in this graph. You are also given a 2D array edges where edges[j] = [aj, bj] indicates that there is a directed edge from node aj to node bj. Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;

impl Solution {
  pub fn largest_path_value(colors: String, edges: Vec<Vec<i32>>) -> i32 {
    let n = colors.len();
    let color_bytes = colors.as_bytes();
    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
    let mut indegree = vec![0u32; n];

    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u].push(v);
      indegree[v] += 1;
    }

    // dp[u][c] = max count of color c on any path ending at u
    let mut dp = vec![[0u32; 26]; n];
    for i in 0..n {
      dp[i][(color_bytes[i] - b'a') as usize] = 1;
    }

    let mut queue: VecDeque<usize> = (0..n).filter(|&i| indegree[i] == 0).collect();
    let mut processed = 0usize;
    let mut ans = 0u32;

    while let Some(u) = queue.pop_front() {
      processed += 1;
      let max_u = *dp[u].iter().max().unwrap();
      ans = ans.max(max_u);

      for &v in &adj[u] {
        let cv = (color_bytes[v] - b'a') as usize;
        for c in 0..26 {
          let new_val = dp[u][c] + if c == cv { 1 } else { 0 };
          if new_val > dp[v][c] {
            dp[v][c] = new_val;
          }
        }
        indegree[v] -= 1;
        if indegree[v] == 0 {
          queue.push_back(v);
        }
      }
    }

    if processed < n { -1 } else { ans as i32 }
  }
}