Longest Path With Different Adjacent Characters

🎯

Longest Path With Different Adjacent Characters

hardGRAPHAmazonGoogle

Imagine you are designing a workflow system where each task depends on others, and you want to find the longest sequence of tasks where no two adjacent tasks share the same category.

💡 This problem involves finding the longest path in a directed acyclic graph (DAG) with an additional constraint on adjacent nodes' labels. Beginners often struggle because it combines graph traversal, topological sorting, and dynamic programming concepts, which require understanding dependencies and state management.

📋

Problem Statement

Given a directed acyclic graph (DAG) with n nodes labeled from 0 to n-1, and a string s of length n where s[i] represents the character label of node i, find the length of the longest path in the graph such that no two adjacent nodes on the path have the same character. The graph is given as a list of edges, where each edge is a pair [u, v] indicating a directed edge from node u to node v. Return the length of the longest valid path. If the graph contains a cycle, return -1.

1 ≤ n ≤ 10^50 ≤ edges.length ≤ 10^5edges[i].length == 20 ≤ edges[i][0], edges[i][1] < ns consists of lowercase English lettersThe graph may be disconnected

💡

Example

Input"n = 5, edges = [[0,1],[1,2],[2,3],[3,4]], s = \"abaca\""

Output3

One longest path is 0 -> 1 -> 2 with characters 'a', 'b', 'a'. Adjacent characters differ, length is 3.

Input"n = 4, edges = [[0,1],[0,2],[2,3],[3,1]], s = \"aabc\""

Output-1

The graph contains a cycle (1 -> 2 -> 3 -> 1), so return -1.

• Graph with no edges → longest path is 1 (single node)
• Graph with all nodes having the same character → longest path is 1
• Graph with multiple disconnected components → consider longest path in any component
• Graph with a cycle → return -1

⚠️

Common Mistakes

Not detecting cycles properly

Infinite recursion or incorrect answer

✅ Use topological sort or track recursion stack to detect cycles

Ignoring character difference constraint

Counting invalid paths with same adjacent characters

✅ Check characters before extending path in DFS or DP

Recomputing longest paths without memoization

Time limit exceeded due to exponential complexity

✅ Cache results with memoization or use iterative DP

Incorrect initialization of DP array

Underestimating path lengths, wrong final answer

✅ Initialize DP with 1 since each node alone forms a path of length 1

Not handling disconnected graph components

Missing longest path in disconnected parts

✅ Process all nodes or components independently

🧠

Brute Force (DFS with Cycle Detection and Path Tracking)

💡 Starting with brute force helps understand the problem's core challenges: detecting cycles and exploring all paths to find the longest valid one. Although inefficient, it lays the foundation for optimization.

Intuition

Try all paths starting from each node using DFS, track the path length only if adjacent characters differ, and detect cycles to avoid infinite loops.

Algorithm

1. For each node, perform a DFS to explore all paths.
2. Track visited nodes to detect cycles; if a cycle is found, return -1.
3. For each path, only continue if the next node's character differs from the current node's character.
4. Keep track of the maximum path length found.

💡 The challenge is managing cycle detection and character constraints simultaneously while exploring all paths, which can be overwhelming at first.

</>

Code

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def longest_path_brute_force(n, edges, s):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = [0] * n  # 0=unvisited, 1=visiting, 2=visited
    max_len = 0

    def dfs(node, prev_char):
        if visited[node] == 1:
            # cycle detected
            return -1
        if visited[node] == 2:
            # already processed
            return 0

        if s[node] == prev_char:
            return 0

        visited[node] = 1
        max_path = 1
        for nei in graph[node]:
            res = dfs(nei, s[node])
            if res == -1:
                return -1
            max_path = max(max_path, 1 + res)
        visited[node] = 2
        return max_path

    for i in range(n):
        res = dfs(i, '')
        if res == -1:
            return -1
        max_len = max(max_len, res)
    return max_len

# Example usage:
if __name__ == '__main__':
    n = 5
    edges = [[0,1],[1,2],[2,3],[3,4]]
    s = "abaca"
    print(longest_path_brute_force(n, edges, s))  # Output: 3

Line Notes

graph = defaultdict(list)Build adjacency list for efficient graph traversal

visited = [0] * nTrack node states to detect cycles and avoid reprocessing

if visited[node] == 1:Detect cycle if node is currently being visited

if s[node] == prev_char:Enforce character difference constraint between adjacent nodes

import java.util.*;

public class LongestPathBruteForce {
    static Map<Integer, List<Integer>> graph = new HashMap<>();
    static int[] visited; // 0=unvisited,1=visiting,2=visited
    static String s;
    static int n;

    public static int dfs(int node, char prevChar) {
        if (visited[node] == 1) return -1; // cycle
        if (visited[node] == 2) return 0;  // processed
        if (s.charAt(node) == prevChar) return 0; // char constraint

        visited[node] = 1;
        int maxPath = 1;
        for (int nei : graph.getOrDefault(node, Collections.emptyList())) {
            int res = dfs(nei, s.charAt(node));
            if (res == -1) return -1;
            maxPath = Math.max(maxPath, 1 + res);
        }
        visited[node] = 2;
        return maxPath;
    }

    public static int longestPath(int nodes, int[][] edges, String labels) {
        n = nodes;
        s = labels;
        visited = new int[n];
        graph.clear();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
        }
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            int res = dfs(i, ' ');
            if (res == -1) return -1;
            maxLen = Math.max(maxLen, res);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{1,2},{2,3},{3,4}};
        String s = "abaca";
        System.out.println(longestPath(n, edges, s)); // Output: 3
    }
}

Line Notes

static Map<Integer, List<Integer>> graphAdjacency list for graph representation

static int[] visitedTrack node visitation state for cycle detection

if (visited[node] == 1) return -1;Detect cycle by revisiting a node in current path

if (s.charAt(node) == prevChar) return 0;Skip paths where adjacent chars are same

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, vector<int>> graph;
vector<int> visited; // 0=unvisited,1=visiting,2=visited
string s;
int n;

int dfs(int node, char prevChar) {
    if (visited[node] == 1) return -1; // cycle
    if (visited[node] == 2) return 0;  // processed
    if (s[node] == prevChar) return 0; // char constraint

    visited[node] = 1;
    int maxPath = 1;
    for (int nei : graph[node]) {
        int res = dfs(nei, s[node]);
        if (res == -1) return -1;
        maxPath = max(maxPath, 1 + res);
    }
    visited[node] = 2;
    return maxPath;
}

int longestPath(int nodes, vector<vector<int>>& edges, string labels) {
    n = nodes;
    s = labels;
    visited.assign(n, 0);
    graph.clear();
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
    }
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        int res = dfs(i, ' ');
        if (res == -1) return -1;
        maxLen = max(maxLen, res);
    }
    return maxLen;
}

int main() {
    int n = 5;
    vector<vector<int>> edges = {{0,1},{1,2},{2,3},{3,4}};
    string s = "abaca";
    cout << longestPath(n, edges, s) << "\n"; // Output: 3
    return 0;
}

Line Notes

unordered_map<int, vector<int>> graph;Use hash map for adjacency list to handle sparse graphs

vector<int> visited;Track node states to detect cycles and avoid recomputation

if (visited[node] == 1) return -1;Cycle detection by revisiting a node in current recursion stack

if (s[node] == prevChar) return 0;Enforce adjacent character difference constraint

function longestPathBruteForce(n, edges, s) {
    const graph = new Map();
    for (const [u, v] of edges) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u).push(v);
    }

    const visited = new Array(n).fill(0); // 0=unvisited,1=visiting,2=visited
    let maxLen = 0;

    function dfs(node, prevChar) {
        if (visited[node] === 1) return -1; // cycle
        if (visited[node] === 2) return 0;  // processed
        if (s[node] === prevChar) return 0; // char constraint

        visited[node] = 1;
        let maxPath = 1;
        const neighbors = graph.get(node) || [];
        for (const nei of neighbors) {
            const res = dfs(nei, s[node]);
            if (res === -1) return -1;
            maxPath = Math.max(maxPath, 1 + res);
        }
        visited[node] = 2;
        return maxPath;
    }

    for (let i = 0; i < n; i++) {
        const res = dfs(i, '');
        if (res === -1) return -1;
        maxLen = Math.max(maxLen, res);
    }
    return maxLen;
}

// Example usage:
const n = 5;
const edges = [[0,1],[1,2],[2,3],[3,4]];
const s = "abaca";
console.log(longestPathBruteForce(n, edges, s)); // Output: 3

Line Notes

const graph = new Map();Build adjacency list using Map for efficient lookups

const visited = new Array(n).fill(0);Track node states to detect cycles and avoid repeated work

if (visited[node] === 1) return -1;Detect cycle by revisiting a node in current DFS path

if (s[node] === prevChar) return 0;Skip paths where adjacent characters are the same

⏱

Complexity

TimeO(n * (n + m)) where m is number of edges

SpaceO(n + m) for graph and recursion stack

DFS from each node can explore many paths; worst case exponential due to repeated states without memoization

💡 For n=20, this approach may do millions of operations, making it impractical for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem and build towards efficient solutions.

🧠

Topological Sort + DFS with Memoization

💡 Memoization avoids recomputing longest paths from nodes by caching results, improving efficiency drastically over brute force.

Intuition

Perform a topological sort to ensure no cycles, then use DFS with memoization to compute the longest valid path from each node, reusing results.

Algorithm

1. Build the graph and compute in-degree of each node.
2. Use Kahn's algorithm to perform topological sort; if cycle detected, return -1.
3. Define a DFS with memoization to compute longest path from each node with character constraints.
4. Return the maximum path length found.

💡 Topological sort guarantees no cycles and orders nodes so dependencies are processed first, making memoization effective.

</>

Code

from collections import defaultdict, deque

def longest_path_memo(n, edges, s):
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    # Kahn's algorithm for topological sort
    queue = deque([i for i in range(n) if indegree[i] == 0])
    topo_order = []
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for nei in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    if len(topo_order) < n:
        return -1  # cycle detected

    memo = [-1] * n

    def dfs(node):
        if memo[node] != -1:
            return memo[node]
        max_len = 1
        for nei in graph[node]:
            if s[nei] != s[node]:
                max_len = max(max_len, 1 + dfs(nei))
        memo[node] = max_len
        return max_len

    max_path = 0
    for node in topo_order:
        max_path = max(max_path, dfs(node))
    return max_path

# Example usage:
if __name__ == '__main__':
    n = 5
    edges = [[0,1],[1,2],[2,3],[3,4]]
    s = "abaca"
    print(longest_path_memo(n, edges, s))  # Output: 3

Line Notes

indegree = [0] * nTrack number of incoming edges for each node to identify start nodes

queue = deque([i for i in range(n) if indegree[i] == 0])Initialize queue with nodes having no dependencies

if len(topo_order) < n:Detect cycle if topological sort does not include all nodes

if s[nei] != s[node]:Enforce adjacent character difference constraint during DFS

import java.util.*;

public class LongestPathMemo {
    public static int longestPath(int n, int[][] edges, String s) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] indegree = new int[n];
        for (int[] e : edges) {
            graph.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
            indegree[e[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            topoOrder.add(node);
            for (int nei : graph.getOrDefault(node, Collections.emptyList())) {
                indegree[nei]--;
                if (indegree[nei] == 0) queue.offer(nei);
            }
        }

        if (topoOrder.size() < n) return -1; // cycle

        int[] memo = new int[n];
        Arrays.fill(memo, -1);

        int maxPath = 0;
        for (int node : topoOrder) {
            maxPath = Math.max(maxPath, dfs(node, graph, s, memo));
        }
        return maxPath;
    }

    private static int dfs(int node, Map<Integer, List<Integer>> graph, String s, int[] memo) {
        if (memo[node] != -1) return memo[node];
        int maxLen = 1;
        for (int nei : graph.getOrDefault(node, Collections.emptyList())) {
            if (s.charAt(nei) != s.charAt(node)) {
                maxLen = Math.max(maxLen, 1 + dfs(nei, graph, s, memo));
            }
        }
        memo[node] = maxLen;
        return maxLen;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{1,2},{2,3},{3,4}};
        String s = "abaca";
        System.out.println(longestPath(n, edges, s)); // Output: 3
    }
}

Line Notes

int[] indegree = new int[n];Count incoming edges to identify nodes without dependencies

Queue<Integer> queue = new LinkedList<>();Use queue for Kahn's topological sort

if (topoOrder.size() < n) return -1;Cycle detection by incomplete topological order

if (s.charAt(nei) != s.charAt(node))Check character difference constraint before DFS

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, vector<int>> graph;
vector<int> indegree, memo;
string s;
int n;

int dfs(int node) {
    if (memo[node] != -1) return memo[node];
    int maxLen = 1;
    for (int nei : graph[node]) {
        if (s[nei] != s[node]) {
            maxLen = max(maxLen, 1 + dfs(nei));
        }
    }
    memo[node] = maxLen;
    return maxLen;
}

int longestPath(int nodes, vector<vector<int>>& edges, string labels) {
    n = nodes;
    s = labels;
    graph.clear();
    indegree.assign(n, 0);
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        indegree[e[1]]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    vector<int> topoOrder;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        topoOrder.push_back(node);
        for (int nei : graph[node]) {
            indegree[nei]--;
            if (indegree[nei] == 0) q.push(nei);
        }
    }

    if ((int)topoOrder.size() < n) return -1; // cycle

    memo.assign(n, -1);
    int maxPath = 0;
    for (int node : topoOrder) {
        maxPath = max(maxPath, dfs(node));
    }
    return maxPath;
}

int main() {
    int n = 5;
    vector<vector<int>> edges = {{0,1},{1,2},{2,3},{3,4}};
    string s = "abaca";
    cout << longestPath(n, edges, s) << "\n"; // Output: 3
    return 0;
}

Line Notes

vector<int> indegree, memo;Track incoming edges and memoized longest paths

queue<int> q;Use queue for Kahn's topological sort

if ((int)topoOrder.size() < n) return -1;Detect cycle if topological order incomplete

if (s[nei] != s[node])Enforce character difference constraint in DFS

function longestPathMemo(n, edges, s) {
    const graph = new Map();
    const indegree = new Array(n).fill(0);
    for (const [u, v] of edges) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u).push(v);
        indegree[v]++;
    }

    const queue = [];
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    const topoOrder = [];
    while (queue.length > 0) {
        const node = queue.shift();
        topoOrder.push(node);
        for (const nei of (graph.get(node) || [])) {
            indegree[nei]--;
            if (indegree[nei] === 0) queue.push(nei);
        }
    }

    if (topoOrder.length < n) return -1; // cycle

    const memo = new Array(n).fill(-1);

    function dfs(node) {
        if (memo[node] !== -1) return memo[node];
        let maxLen = 1;
        for (const nei of (graph.get(node) || [])) {
            if (s[nei] !== s[node]) {
                maxLen = Math.max(maxLen, 1 + dfs(nei));
            }
        }
        memo[node] = maxLen;
        return maxLen;
    }

    let maxPath = 0;
    for (const node of topoOrder) {
        maxPath = Math.max(maxPath, dfs(node));
    }
    return maxPath;
}

// Example usage:
const n = 5;
const edges = [[0,1],[1,2],[2,3],[3,4]];
const s = "abaca";
console.log(longestPathMemo(n, edges, s)); // Output: 3

Line Notes

const indegree = new Array(n).fill(0);Count incoming edges to find start nodes

const queue = [];Queue for Kahn's topological sort

if (topoOrder.length < n) return -1;Cycle detection by incomplete topological order

if (s[nei] !== s[node])Check character difference before recursive DFS call

⏱

Complexity

TimeO(n + m) where m is number of edges

SpaceO(n + m) for graph, memo, and recursion stack

Topological sort is O(n+m), DFS with memoization visits each node once, so total linear time

💡 For n=10^5, this approach is efficient enough to run within seconds.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs, making it the preferred solution in interviews.

🧠

Topological Sort + Iterative DP

💡 Using iterative DP over topological order avoids recursion and stack overhead, which can be beneficial in some languages or environments.

Intuition

After topological sorting, compute the longest valid path length for each node iteratively by checking all incoming edges and character constraints.

Algorithm

1. Build graph and compute in-degree for each node.
2. Perform topological sort using Kahn's algorithm; return -1 if cycle detected.
3. Initialize a DP array with 1 for each node (minimum path length).
4. Iterate over nodes in topological order, update DP for neighbors if characters differ.
5. Return the maximum value in DP array.

💡 This approach is easier to debug and avoids recursion limits, but requires careful update of DP values respecting character constraints.

</>

Code

from collections import defaultdict, deque

def longest_path_iterative(n, edges, s):
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(n) if indegree[i] == 0])
    topo_order = []
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for nei in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    if len(topo_order) < n:
        return -1

    dp = [1] * n
    for node in topo_order:
        for nei in graph[node]:
            if s[nei] != s[node]:
                dp[nei] = max(dp[nei], dp[node] + 1)

    return max(dp)

# Example usage:
if __name__ == '__main__':
    n = 5
    edges = [[0,1],[1,2],[2,3],[3,4]]
    s = "abaca"
    print(longest_path_iterative(n, edges, s))  # Output: 3

Line Notes

dp = [1] * nInitialize DP with 1 since each node alone forms a path of length 1

for node in topo_order:Process nodes in topological order to ensure dependencies are handled

if s[nei] != s[node]:Only update DP if adjacent characters differ

dp[nei] = max(dp[nei], dp[node] + 1)Update longest path to neighbor considering current node

import java.util.*;

public class LongestPathIterative {
    public static int longestPath(int n, int[][] edges, String s) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] indegree = new int[n];
        for (int[] e : edges) {
            graph.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
            indegree[e[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            topoOrder.add(node);
            for (int nei : graph.getOrDefault(node, Collections.emptyList())) {
                indegree[nei]--;
                if (indegree[nei] == 0) queue.offer(nei);
            }
        }

        if (topoOrder.size() < n) return -1;

        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int node : topoOrder) {
            for (int nei : graph.getOrDefault(node, Collections.emptyList())) {
                if (s.charAt(nei) != s.charAt(node)) {
                    dp[nei] = Math.max(dp[nei], dp[node] + 1);
                }
            }
        }

        int maxPath = 0;
        for (int val : dp) maxPath = Math.max(maxPath, val);
        return maxPath;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{1,2},{2,3},{3,4}};
        String s = "abaca";
        System.out.println(longestPath(n, edges, s)); // Output: 3
    }
}

Line Notes

int[] dp = new int[n];DP array to store longest path lengths ending at each node

Arrays.fill(dp, 1);Each node alone forms a path of length 1

for (int node : topoOrder)Process nodes in topological order to respect dependencies

dp[nei] = Math.max(dp[nei], dp[node] + 1);Update DP for neighbor if character constraint satisfied

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, vector<int>> graph;
vector<int> indegree, dp;
string s;
int n;

int longestPath(int nodes, vector<vector<int>>& edges, string labels) {
    n = nodes;
    s = labels;
    graph.clear();
    indegree.assign(n, 0);
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        indegree[e[1]]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    vector<int> topoOrder;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        topoOrder.push_back(node);
        for (int nei : graph[node]) {
            indegree[nei]--;
            if (indegree[nei] == 0) q.push(nei);
        }
    }

    if ((int)topoOrder.size() < n) return -1;

    dp.assign(n, 1);
    for (int node : topoOrder) {
        for (int nei : graph[node]) {
            if (s[nei] != s[node]) {
                dp[nei] = max(dp[nei], dp[node] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

int main() {
    int n = 5;
    vector<vector<int>> edges = {{0,1},{1,2},{2,3},{3,4}};
    string s = "abaca";
    cout << longestPath(n, edges, s) << "\n"; // Output: 3
    return 0;
}

Line Notes

dp.assign(n, 1);Initialize DP with 1 since each node alone forms a path

for (int node : topoOrder)Process nodes in topological order to ensure dependencies are met

if (s[nei] != s[node])Check character difference constraint before updating DP

dp[nei] = max(dp[nei], dp[node] + 1);Update longest path length for neighbor

function longestPathIterative(n, edges, s) {
    const graph = new Map();
    const indegree = new Array(n).fill(0);
    for (const [u, v] of edges) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u).push(v);
        indegree[v]++;
    }

    const queue = [];
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    const topoOrder = [];
    while (queue.length > 0) {
        const node = queue.shift();
        topoOrder.push(node);
        for (const nei of (graph.get(node) || [])) {
            indegree[nei]--;
            if (indegree[nei] === 0) queue.push(nei);
        }
    }

    if (topoOrder.length < n) return -1;

    const dp = new Array(n).fill(1);
    for (const node of topoOrder) {
        for (const nei of (graph.get(node) || [])) {
            if (s[nei] !== s[node]) {
                dp[nei] = Math.max(dp[nei], dp[node] + 1);
            }
        }
    }

    return Math.max(...dp);
}

// Example usage:
const n = 5;
const edges = [[0,1],[1,2],[2,3],[3,4]];
const s = "abaca";
console.log(longestPathIterative(n, edges, s)); // Output: 3

Line Notes

const dp = new Array(n).fill(1);Initialize DP array with 1 for single-node paths

for (const node of topoOrder)Process nodes in topological order to respect dependencies

if (s[nei] !== s[node])Check character difference constraint before updating DP

dp[nei] = Math.max(dp[nei], dp[node] + 1);Update DP for neighbor with longest path length

⏱

Complexity

TimeO(n + m)

SpaceO(n + m)

Topological sort and DP updates each run in linear time relative to nodes and edges

💡 This approach is efficient and avoids recursion, suitable for large inputs and strict stack limits.

Interview Verdict: Accepted

Iterative DP is a robust alternative to recursion, often preferred in production code.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the topological sort + memoization approach is usually best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * (n + m)) exponential worst case	O(n + m) for graph and recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Topological Sort + DFS with Memoization	O(n + m)	O(n + m)	Possible but less likely	Yes (with extra parent tracking)	Preferred approach to code
3. Topological Sort + Iterative DP	O(n + m)	O(n + m)	No	Yes (with extra parent tracking)	Good alternative if recursion is restricted

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem constraints and ask about cycles and character constraints.Start with brute force DFS to show understanding of graph traversal and cycle detection.Explain inefficiency and introduce topological sort to detect cycles and order nodes.Add memoization to optimize repeated computations.Optionally, present iterative DP to avoid recursion.Discuss time and space complexities and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Optimize: 7min. Total ~30min

What the Interviewer Tests

Ability to detect cycles, apply topological sorting, implement memoization or DP, and handle character constraints correctly.

Common Follow-ups

• What if the graph is not a DAG? → Return -1 or detect cycle early.
• Can you reconstruct the longest path? → Store predecessors during DP and backtrack.

💡 These follow-ups test your understanding of graph properties and ability to extend solutions beyond just length calculation.

🔍

Pattern Recognition

When to Use

Use this pattern when you have a DAG and need to find longest paths with additional constraints, especially when cycles must be detected and adjacency conditions apply.

Signature Phrases

'longest path in a directed graph''no two adjacent nodes have the same character''return -1 if cycle exists'

NOT This Pattern When

Shortest path problems, undirected graphs without DAG constraints, or problems without adjacency character constraints

Similar Problems

Longest Path in a Directed Acyclic Graph - classic longest path problemLongest Increasing Path in a Matrix - similar DP on DAG with constraints

Practice

1. Consider the following Python code implementing the optimal approach to find eventual safe states. Given the input graph = [[1],[2],[3],[]], what is the final returned list of safe nodes?

from collections import deque

def eventualSafeNodes(graph):
    n = len(graph)
    reverse_graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u in range(n):
        for v in graph[u]:
            reverse_graph[v].append(u)
        in_degree[u] = len(graph[u])

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    safe = []

    while queue:
        node = queue.popleft()
        safe.append(node)
        for prev in reverse_graph[node]:
            in_degree[prev] -= 1
            if in_degree[prev] == 0:
                queue.append(prev)

    return sorted(safe)

easy

A. [3]

B. [0, 3]

C. [0, 1, 2, 3]

D. [1, 2, 3]

Solution

1. Step 1: Initialize in-degree and reverse graph

   Graph has edges: 0->1, 1->2, 2->3, 3->none. So in_degree = [1,1,1,0], reverse_graph = [[],[0],[1],[2]].

2. Step 2: Process queue starting with nodes having in-degree 0

   Start with node 3 in queue. Pop 3, safe=[3]. Decrement in_degree of 2 to 0, add 2 to queue. Pop 2, safe=[3,2]. Decrement in_degree of 1 to 0, add 1. Pop 1, safe=[3,2,1]. Decrement in_degree of 0 to 0, add 0. Pop 0, safe=[3,2,1,0].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All nodes lead to terminal node 3, so all are safe [OK]

Hint: Nodes with zero out-degree start the safe node chain [OK]

Common Mistakes:

• Forgetting to sort final safe list
• Miscounting in-degree initialization
• Off-by-one errors in queue processing

2. Consider the following Python code implementing the optimal approach for minimum semesters. Given n = 3 and relations = [[1,3],[2,3]], what is the value of semester returned by the function?

from collections import deque, defaultdict

def min_semesters_optimal(n, relations):
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    for u, v in relations:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
    semester = 0
    processed = 0

    while queue:
        semester += 1
        for _ in range(len(queue)):
            course = queue.popleft()
            processed += 1
            for nei in graph[course]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

    return semester if processed == n else -1

print(min_semesters_optimal(3, [[1,3],[2,3]]))

easy

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Initialize graph and indegree

   Courses 1 and 2 have indegree 0, course 3 has indegree 2.

2. Step 2: Process BFS levels

   Semester 1: process courses 1 and 2 (both indegree 0), decrement indegree of 3 twice -> indegree[3] becomes 0, add 3 to queue. Semester 2: process course 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two BFS levels -> 2 semesters [OK]

Hint: Courses with zero indegree processed per semester [OK]

Common Mistakes:

• Counting each course as a separate semester
• Off-by-one error in semester increment
• Returning -1 incorrectly when all courses processed

3. Examine the following code snippet for the largest color value problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

from collections import defaultdict, deque

def largestPathValue(colors, edges):
    n = len(colors)
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    dp = [[0]*26 for _ in range(n)]
    queue = deque([i for i in range(n) if indegree[i] == 0])
    count = 0
    max_color_value = 0

    while queue:
        node = queue.popleft()
        count += 1
        c_index = ord(colors[node]) - ord('a')
        dp[node][c_index] += 1
        max_color_value = max(max_color_value, dp[node][c_index])

        for nei in graph[node]:
            for i in range(26):
                dp[nei][i] = max(dp[nei][i], dp[node][i])
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    if count != n:
        return -1  # cycle detected
    return max_color_value

medium

A. Line incrementing dp[node][c_index]

B. Line updating dp[nei][i] inside the nested loop

C. Line checking if count != n to detect cycles

D. Line initializing the queue with nodes having indegree zero

Solution

1. Step 1: Understand dp update logic

   dp[nei][i] should aggregate max counts from predecessors, but the code overwrites dp[nei][i] without adding the neighbor's own color count.

2. Step 2: Identify bug

   The bug is that dp[nei][i] = max(dp[nei][i], dp[node][i]) does not add the neighbor's own color count, causing undercounting.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect aggregation leads to wrong max color values [OK]

Hint: Check if dp updates correctly accumulate color counts [OK]

Common Mistakes:

• Not aggregating color counts from neighbors properly

4. Examine the following code snippet for finding Minimum Height Trees. Which line contains a subtle bug that causes incorrect results on single-node trees?

medium

A. Missing explicit check for n == 1 at the start

B. Line initializing leaves with nodes of degree 1

C. Line decrementing remaining_nodes by leaves_count

D. Line updating degree[nei] after removing a leaf

Solution

1. Step 1: Identify edge case handling

   The code lacks a special case for n=1, so leaves initialization is empty and the loop never runs, returning an empty list.

2. Step 2: Understand impact of missing check

   Without returning [0] for single-node tree, the function returns incorrect empty result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single-node tree must be handled explicitly [OK]

Hint: Check for single-node tree before main logic [OK]

Common Mistakes:

• Forgetting n=1 case
• Incorrect leaves initialization
• Not updating degrees properly

5. What is the time complexity of the optimal DFS postorder topological sort approach for sequence reconstruction, given n as the length of the original sequence and m as the total length of all sequences in seqs?

medium

A. O(n + m)

B. O(n! * m)

C. O(n * m)

D. O(m^2)

Solution

1. Step 1: Identify graph construction cost

   Building graph from seqs takes O(m) time, where m is total length of all sequences.

2. Step 2: Analyze DFS traversal cost

   DFS visits each node once and edges once, total O(n + m). No extra factorial or quadratic factors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in nodes plus edges [OK]

Hint: DFS topo sort is O(V+E) -> O(n+m) here [OK]

Common Mistakes:

• Confusing with brute force factorial complexity
• Assuming quadratic due to nested loops