Last Updated: 9 Jan, 2021
Max Path Value
Moderate
Asked in companies
You are given a directed graph with ‘N’ nodes and ‘M’ edges. Each node has a lowercase letter assigned to it. For any path, the path’s value is defined as the maximum frequency of a letter on the path. You are supposed to find the maximum value of a path. If the maximum value can be infinitely large then return -1.
Example:
If some path has the letters “xyxxxyzz” then the value of this path will be 4 as the maximum frequency of any letter(‘x’) is 4.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.
The first line of each test case contains two integers separated by a single space ‘N’ and ‘M’ denoting the number of the nodes and the number of edges respectively.
The next line contains a string of length ‘N’ consisting of lowercase letters, denoting the character assigned to each node. The 'i’-th character of the string is assigned to the 'i’-th node.
The next ‘M’ lines of each test case contain two integers, ‘X’ and ‘Y’ separated by a single space, ‘X’ and ’Y’ denote the vertices connected by an edge directed from ‘X’ to ‘Y’.
Output Format:
For each test case, return the maximum value of any path.
Note:
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10^5
0 <= M <= 10^5
|S| = N
1 <= X,Y <= N
Where |S| denotes the length of the string.
Time limit: 1 sec
Approaches
The idea is to explore all possible paths and then take the maximum value out of all the paths.
We can see that if the graph contains a cycle then we can keep traversing the cycle, again and again, hence the answer will be infinitely large, thus in case a cycle is present in the graph we should return -1.
For finding a cycle we will use the depth first search algorithm, to check whether any back edge exists in the graph or not. If we find any back edge then that means there exists a cycle in the graph.
The steps are as follows:
- Iterate through the edges and insert each edge into an adjacency list.
- Iterate from 1 to ‘N’, let’s say we are currently at ‘i’.
- Do a Depth-first Search starting from the 'i'-th node to explore all possible paths starting from the 'i'-th node.
- Keep track of the frequency of characters during the Depth First Search.
- For every path starting from the 'i’-th node calculate the maximum frequency of the characters.
- The maximum frequency of a letter out of all paths will be the answer.
The idea is to use dynamic programming so that we don’t traverse any node more than once.
Let’s define a 2-D array ‘dp’, ‘dp[i][j]’ will denote the maximum number of letters ‘j’ that we can have when we reach the i’th node. (We will denote ‘a’ by 0, ‘b’ with 1, and so on). The value of ‘i’ will range from 1 to N and the value of ‘j’ will range from 0 to 25 since there are 26 distinct characters. In order to get the value ‘dp[i][j]’, we will need to visit all nodes which have an edge directed towards node ‘i’ before visiting the i’th node. Thus we follow the topological sorting order when visiting the nodes.
We can see that if the graph contains a cycle then we can keep traversing the cycle, again and again, hence the answer will be infinitely large, thus in case a cycle is present in the graph we should return -1.
The steps are as follows :
- Let’s define an array ‘inDegree’ to keep track of the indegree of each node. Initially, all elements in ‘inDegree’ are equal to 0.
- Iterate through the edges and insert each edge into an adjacency list, let’s say the current edge is directed to node ‘X’ then increment ‘inDegree[X]’ by 1.
- We will use a queue to traverse the nodes in the topological order. Initially, we will push nodes with ‘inDegree’ equal to 0 in the queue.
- We will pop the element at the front of the queue, let’s say this element is ‘current’.
- Let’s say the character assigned to this node is ‘C’.
- Increment ‘dp['current'][’C']' by 1.
- Iterate through all edges starting from ‘current’ node, let’s say the current edge points to node ‘X’.
- Iterate from 0 to 25, let’s say the current index is ‘j’.
- Update ‘dp[’X']['j']' by max('dp['X']['j']', ‘dp[’current']['j']').
- Decrease 'inDegree['X']' by 1.
- If ‘inDegree[’X']' is 0 that means all nodes having an edge directed to ‘X’, have been visited already, hence we will push ‘X’ to the back of the queue.
- If after ‘N’ pop operations there are still some elements present in the queue that means that the given graph has a cycle, hence we will return -1.
- Otherwise, we will iterate through all the elements of the ‘dp’ array and return the maximum element.