Largest Single-Color Run Along a Pipeline Path
A data pipeline is a directed graph of stages, each tagged with a color (a processing category). Along any path, find the maximum number of nodes sharing one color; report -1 if the graph has a cycle.
Problem
Given a directed graph of n nodes (0-indexed) where colors is a string with colors[i] the color of node i, and edges is a list of directed edges [u, v], the value of a path is the largest count of any single color among the nodes on it. Return the maximum value over all paths, or -1 if the graph contains a cycle.
Input
A string colors of lowercase letters and a list edges of directed [u, v] pairs.
Output
An integer: the maximum single-color path value, or -1 on a cycle.
Constraints
- 1 <= n <= 100000
- 0 <= edges.length <= 100000
- colors consists of lowercase English letters.
Examples
Example 1
Input
colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output
3
The path 0->2->3->4 has color 'a' appearing 3 times.
Example 2
Input
colors = "a", edges = [[0,0]]
Output
-1
The self-loop is a cycle.