1857. Largest Color Value in a Directed Graph

Hard

1.8K

61

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 `i`

node in this graph (^{th}**0-indexed**). You are also given a 2D array `edges`

where `edges[j] = [a`

indicates that there is a _{j}, b_{j}]**directed edge** from node `a`

to node _{j}`b`

._{j}

A valid **path** in the graph is a sequence of nodes `x`

such that there is a directed edge from _{1} -> x_{2} -> x_{3} -> ... -> x_{k}`x`

to _{i}`x`

for every _{i+1}`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`

**Example 1:**

Input:colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]Output:3Explanation: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:-1Explanation:There is a cycle from 0 to 0.

**Constraints:**

`n == colors.length`

`m == edges.length`

`1 <= n <= 10`

^{5}`0 <= m <= 10`

^{5}`colors`

consists of lowercase English letters.`0 <= a`

_{j}, b_{j}< n

Accepted

55.4K

Submissions

106.7K

Acceptance Rate

51.9%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved