I solved this problem using a topological sort because the presence of a cycle would make it impossible to define valid paths. I used Kahn's algorithm to detect cycles and simultaneously calculated the most frequent color occurrences using dynamic programming. For each node, I maintained a frequency table for all 26 lowercase letters. When visiting a node's neighbor, I propagated the color frequencies accordingly. Finally, if all nodes were visited, I returned the maximum color frequency seen on any path; otherwise, I returned -1 for the cycle case.
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
graph = defaultdict(list)
indegree = [0] * n
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
color_count = [[0] * 26 for _ in range(n)]
queue = deque()
for i in range(n):
if indegree[i] == 0:
queue.append(i)
color_count[i][ord(colors[i]) - ord('a')] = 1
visited = 0
max_color_value = 0
while queue:
u = queue.popleft()
visited += 1
curr_color_val = max(color_count[u])
max_color_value = max(max_color_value, curr_color_val)
for v in graph[u]:
for c in range(26):
color_val = color_count[u][c] + (1 if c == ord(colors[v]) - ord('a') else 0)
color_count[v][c] = max(color_count[v][c], color_val)
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return max_color_value if visited == n else -1- Time: O(n + m), where n is the number of nodes and m is the number of edges.
- Space: O(n + m + 26 * n) for graph, indegrees, and color count tracking.
