Problem

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.

The graph is represented with a string and an edge list. The i-th character represents the uppercase letter of the i-th node. Each tuple in the edge list (i, j) means there is a directed edge from the i-th node to the j-th node. Self-edges are possible, as well as multi-edges.

Examples

Example 1:

graph TD;
	A --> B & A1("A")
	A1 --> C
	C --> A2("A")

	
linkStyle 1 stroke:gold, stroke-width:4px;
linkStyle 2 stroke:gold, stroke-width:4px;
linkStyle 3 stroke:gold, stroke-width:4px;
  
Input: nodes = "ABACA", edges =[[0, 1], [0, 2], [2, 3], [3, 4]]
Output: 3
Explanation: Would have maximum value 3 using the path of vertices `[0, 2, 3, 4]`, `(A, A, C, A)`.

Solution

Method 1 - Run DFS with memoization and detect Cycle

To solve this problem, we need to traverse the directed graph and find the path with the maximum count of the most frequently occurring letter. Additionally, we need to detect cycles in the graph to handle infinite loops.

Steps:

  1. Build the graph using an adjacency list.

  2. Cycle Detection:

    • Use Depth-First Search (DFS) to detect cycles in the graph. If a cycle is detected, return null.

  3. DFS with Frequency Counts:

    • Traverse the graph using DFS to track the count of each letter along the path.
    • Maintain a 2D array to store the frequency count of each letter at each node.

  4. Track Maximum Value:

    • Keep track of the maximum count of any letter encountered during the traversal.

Code

Java
public class LargestPathValue {

	private int[][] letterCount;
	private char[] letters;
	private List<Integer> [] graph;
	private int[] visited;
	private int[] dp;

	private boolean hasCycle = false;

	public Integer largestPathValue(String nodes, int[][] edges) {
		int n = nodes.length();
		graph = new List[n];

		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int[] edge: edges) {
			graph[edge[0]].add(edge[1]);
		}

		letters = nodes.toCharArray();
		letterCount = new int[n][26];
		visited = new int[n];
		dp = new int[n];
		Arrays.fill(dp, -1);

		int maxValue = 0;

		for (int i = 0; i < n; i++) {
			int value = dfs(i);

			if (value == -1) return null;
			maxValue = Math.max(maxValue, value);
		}

		return maxValue;
	}

	private int dfs(int node) {
		if (dp[node] != -1) return dp[node];

		if (visited[node] == 2) return -1;

		visited[node] = 2;
		int maxFreq = 0;
		int idx = letters[node] - 'A';

		letterCount[node][idx] = 1;

		for (int neighbor: graph[node]) {
			int res = dfs(neighbor);

			if (res == -1) return -1;

			for (int i = 0; i < 26; i++) {
				letterCount[node][i] = Math.max(letterCount[node][i], (i == idx ? 1 : 0) + letterCount[neighbor][i]);
				maxFreq = Math.max(maxFreq, letterCount[node][i]);
			}
		}

		visited[node] = 1;
		dp[node] = maxFreq;
		return dp[node];
	}
}

Complexity

  • ⏰ Time complexity: O(n + m)
    • Building the adjacency list from the edges takes (O(m)), where (m) is the number of edges.
    • For each node, the DFS processes every neighbor (edge) exactly once.
  • 🧺 Space complexity: O(n + m)
    • The adjacency list requires (O(n + m)) space, where (n) is the number of nodes and (m) is the number of edges. Each node’s list holds references to its neighbors.
    • Arrays such as visited and dp take O(n) space
    • 2D array letterCount for tracking letter frequencies:
      • letterCount has dimensions (n \times 26), resulting in (O(26n)) space.
    • Overall, this is equivalent to (O(n)) in higher-level space complexity terms since (26) is a constant.