Max Path Value

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
76 upvotes
Asked in companies
AccoliteFlipkart limited

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 5
abcdef
1 2
2 3
4 2
4 3
1 3
3 3
aba
1 2
2 3
1 3
Sample Output 1 :
1
2
Explanation of Sample Output 1 :
In test case 1, for any path in the graph, the maximum frequency of a letter will be 1.

In test case 2, the path from 1->2->3 will have a maximum frequency 2 of the letter ‘a’.
Sample Input 2 :
2
4 3
abab
1 2
2 4
4 1
2 1
aa
1 2
Sample Output 2 :
-1
2
Explanation of Sample Output 2 :
In test case 1, the answer can be infinitely large hence the output is -1.

In test case 2, there is only 1 path from 1->2 which has a maximum frequency of 2.


Hints:
1. Try to find all the path starting from every node of the graph.    
2. Think about some dynamic programming state that takes care of both node and some letter frequency.
Approaches (2)
Brute force Approach

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:

 

  1. Iterate through the edges and insert each edge into an adjacency list.
  2. 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.
  3. For every path starting from the 'i’-th node calculate the maximum frequency of the characters.
  4. The maximum frequency of a letter out of all paths will be the answer.
Time Complexity

O(N ^ 2), Where ‘N’ is the number of nodes in the graph.

 

Since we are finding all possible paths in the graph which in the worst case(bamboo-like graph) will be of the order of N ^ 2. Thus, the overall time complexity is O(N ^ 2).

Space Complexity

O(N), Where ‘N’ is the number of nodes in the graph.

 

Since we are creating adjacency lists for storing edges which will take O(N) space. Thus, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Max Path Value
Full screen
Console