Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 (0-indexed). 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.
A valid path in the graph is a sequence of nodes x1 -> x2 -> x3 -> ... -> xk such that there is a directed edge from xi to xi+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.
Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.
Example 1:
Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).
Example 2:
Input: colors = "a", edges = [[0,0]] Output: -1 Explanation: There is a cycle from 0 to 0.
Constraints:
n == colors.lengthm == edges.length1 <= n <= 1050 <= m <= 105colors consists of lowercase English letters.0 <= aj, bj < nProblem summary: 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 (0-indexed). 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. A valid path in the graph is a sequence of nodes x1 -> x2 -> x3 -> ... -> xk such that there is a directed edge from xi to xi+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path. Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Dynamic Programming · Topological Sort
"abaca" [[0,1],[0,2],[2,3],[3,4]]
"a" [[0,0]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1857: Largest Color Value in a Directed Graph
class Solution {
public int largestPathValue(String colors, int[][] edges) {
int n = colors.length();
List<Integer>[] g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) {
int a = e[0], b = e[1];
g[a].add(b);
++indeg[b];
}
Deque<Integer> q = new ArrayDeque<>();
int[][] dp = new int[n][26];
for (int i = 0; i < n; ++i) {
if (indeg[i] == 0) {
q.offer(i);
int c = colors.charAt(i) - 'a';
++dp[i][c];
}
}
int cnt = 0;
int ans = 1;
while (!q.isEmpty()) {
int i = q.pollFirst();
++cnt;
for (int j : g[i]) {
if (--indeg[j] == 0) {
q.offer(j);
}
int c = colors.charAt(j) - 'a';
for (int k = 0; k < 26; ++k) {
dp[j][k] = Math.max(dp[j][k], dp[i][k] + (c == k ? 1 : 0));
ans = Math.max(ans, dp[j][k]);
}
}
}
return cnt == n ? ans : -1;
}
}
// Accepted solution for LeetCode #1857: Largest Color Value in a Directed Graph
func largestPathValue(colors string, edges [][]int) int {
n := len(colors)
g := make([][]int, n)
indeg := make([]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
indeg[b]++
}
q := []int{}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, 26)
}
for i, v := range indeg {
if v == 0 {
q = append(q, i)
c := colors[i] - 'a'
dp[i][c]++
}
}
cnt := 0
ans := 1
for len(q) > 0 {
i := q[0]
q = q[1:]
cnt++
for _, j := range g[i] {
indeg[j]--
if indeg[j] == 0 {
q = append(q, j)
}
c := int(colors[j] - 'a')
for k := 0; k < 26; k++ {
t := 0
if c == k {
t = 1
}
dp[j][k] = max(dp[j][k], dp[i][k]+t)
ans = max(ans, dp[j][k])
}
}
}
if cnt == n {
return ans
}
return -1
}
# Accepted solution for LeetCode #1857: Largest Color Value in a Directed Graph
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
indeg = [0] * n
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
indeg[b] += 1
q = deque()
dp = [[0] * 26 for _ in range(n)]
for i, v in enumerate(indeg):
if v == 0:
q.append(i)
c = ord(colors[i]) - ord('a')
dp[i][c] += 1
cnt = 0
ans = 1
while q:
i = q.popleft()
cnt += 1
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
c = ord(colors[j]) - ord('a')
for k in range(26):
dp[j][k] = max(dp[j][k], dp[i][k] + (c == k))
ans = max(ans, dp[j][k])
return -1 if cnt < n else ans
// Accepted solution for LeetCode #1857: Largest Color Value in a Directed Graph
use std::collections::VecDeque;
impl Solution {
pub fn largest_path_value(colors: String, edges: Vec<Vec<i32>>) -> i32 {
let n = colors.len();
let mut graph = vec![vec![]; n];
let mut indegree = vec![0; n];
for edge in edges {
let u = edge[0] as usize;
let v = edge[1] as usize;
graph[u].push(v);
indegree[v] += 1;
}
let mut queue = VecDeque::new();
for i in 0..n {
if indegree[i] == 0 {
queue.push_back(i);
}
}
let mut color_count = vec![vec![0; 26]; n];
let mut visited = 0;
let colors = colors.as_bytes();
let mut max_color_value = 0;
while let Some(node) = queue.pop_front() {
visited += 1;
let color_index = (colors[node] - b'a') as usize;
color_count[node][color_index] += 1;
max_color_value = max_color_value.max(color_count[node][color_index]);
for &neigh in &graph[node] {
for i in 0..26 {
color_count[neigh][i] = color_count[neigh][i].max(color_count[node][i]);
}
indegree[neigh] -= 1;
if indegree[neigh] == 0 {
queue.push_back(neigh);
}
}
}
if visited != n as i32 {
return -1;
}
max_color_value
}
}
// Accepted solution for LeetCode #1857: Largest Color Value in a Directed Graph
function largestPathValue(colors: string, edges: number[][]): number {
const n = colors.length;
const indeg = Array(n).fill(0);
const g: Map<number, number[]> = new Map();
for (const [a, b] of edges) {
if (!g.has(a)) g.set(a, []);
g.get(a)!.push(b);
indeg[b]++;
}
const q: number[] = [];
const dp: number[][] = Array.from({ length: n }, () => Array(26).fill(0));
for (let i = 0; i < n; i++) {
if (indeg[i] === 0) {
q.push(i);
const c = colors.charCodeAt(i) - 97;
dp[i][c]++;
}
}
let cnt = 0;
let ans = 1;
while (q.length) {
const i = q.pop()!;
cnt++;
if (g.has(i)) {
for (const j of g.get(i)!) {
indeg[j]--;
if (indeg[j] === 0) q.push(j);
const c = colors.charCodeAt(j) - 97;
for (let k = 0; k < 26; k++) {
dp[j][k] = Math.max(dp[j][k], dp[i][k] + (c === k ? 1 : 0));
ans = Math.max(ans, dp[j][k]);
}
}
}
}
return cnt < n ? -1 : ans;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.