Most Repeated Colour on a Path

Hard

You have a directed graph with n nodes numbered 0 to n - 1. Every node is painted: node i has the colour given by the letter colors[i]. The edges are listed in links, where links[j] = [a, b] is an edge from a to b. A path is a sequence of nodes where each node has an edge to the next one (a single node is a path too). The value of a path is how many times its most frequent colour appears on it. Return the largest value over all paths in the graph. If the graph contains a cycle, return -1.

Example 1

colors="rgrbr", links=[[0, 1], [1, 2], [0, 3], [3, 2], [2, 4]] → 3

The path 0 → 1 → 2 → 4 visits three nodes coloured r (0, 2 and 4); no path does better.

Example 2

colors="xyx", links=[[0, 1], [1, 2], [2, 1]] → -1

Nodes 1 and 2 form a cycle, so the answer is -1.

Example 3

colors="qq", links=[] → 1

Constraints

n == len(colors)
1 ≤ n ≤ 10⁵
0 ≤ len(links) ≤ 10⁵
colors consists of lowercase English letters
0 ≤ a, b < n

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Topological Sort Memoization Hash Table Dynamic Programming Counting

Similar problems

Longest Uphill Walk Hard Thief and Guard Hard Mouse, Cat and Cheese Hard Uphill-Only Walks Hard Every Way to Space the Words Hard

Input

colors="rgrbr", links=[[0, 1], [1, 2], [0, 3], [3, 2], [2, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.