I came across the largest value path problem yesterday, and this blog post outlines my thought process on how I visualized it. I did not figure out a concrete solution, but I think I got a good outline on an approach

The first part of the description goes as follows -

In a directed graph, each node is assigned an uppercase letter. We define a path's value as the number of most frequently-occurring letter along that path. For example, if a path in the graph goes through "ABACA", the value of the path is 3, since there are 3 occurrences of 'A' on the path.

Given a graph with n nodes and m directed edges, return the largest value path of the graph. If the largest value is infinite, then return null.

and here is the rest -

This is classified as a hard problem, and it did take me some time to go through the details and understand what is being asked.

# Inputs

Firstly, the inputs are represented as

- a String ,
- and a 2D array.

# Infinite Sum ?

# Longest or Largest ?

I had conflated largest with longest, and assumed that I had to fine the longest path. **No**, I had to find the path with the largest occurrences of a single character. This meant, I had to go through ALL the paths and return the number of occurrences of the often seen character and then find the max of all the paths. This sounds like I will need to use a DFS with back tracking

# Solution ?

#### How To Traverse

- This is directed graph, we could do one pass over the String, and figure out which of these characters are roots.
- The root is a character that has not edges pointing to it.
- The edges could be stored in a quick lookup data structure to facilitate this .
- For all the roots do a DFS with Backtracking and use a memo to find the max occurrent character within each root
- Finally, we just need to figure out the max for all roots
- TBD - how to determine if there is a cycle