Largest value path of a graph

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. 

The 2D array contains the edges. Each number in the edge corresponds to the character position in the String. Drawing a picture of the graph help greatly if you are not very familiar with graphs

Infinite Sum ?

What's this about returning a null value for an infinite sum ? Rereading the problem, we are apparently given a directed graph and it is possible for the graph to have loops.

In these situations we should return null. From a CS course, I do remember that there is a way to detect cycles. In our case, I am assuming that I can keep track of nodes visited and detect a cycle, and return null

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

Also, there is no single root (pic below). I would have to separately keep track of whether all the characters in the String were visited. perhaps using an array.

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