Largest Color Value in a Directed Graph

HardGraphstopological sort

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A directed graph has n nodes labeled 0 to n - 1. colors[i] is the lowercase letter color of node i, and edges[j] = [a_j, b_j] is a directed edge from a_j to b_j. Along any directed path, the **color value** is the number of nodes on the path that share the most frequent color. For example, a path colored a, b, a has color value 2. Return the largest color value over all directed paths in the graph (a single node is a path of value 1), or -1 if the graph contains a directed cycle (including a self-loop).

Examples

Input: colors = "abbab", edges = [[0,1],[1,2],[2,4],[0,3],[3,4]]
Output: 3
The path `0 -> 1 -> 2 -> 4` has colors `a, b, b, b`, so color `b` appears 3 times.
Input: colors = "xy", edges = [[0,1],[1,0]]
Output: -1
Nodes 0 and 1 form a cycle.
Input: colors = "q", edges = []
Output: 1
The single node is a path with color value 1.

Constraints

  • `n == colors.length`
  • `1 <= n <= 10^5`
  • `0 <= edges.length <= 10^5`
  • `0 <= a_j, b_j < n`
  • `colors` consists of lowercase English letters

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More topological sort problems