Longest Path With Different Adjacent Characters

▶

Steps

setup

Build graph and compute in-degree

We initialize the graph adjacency list and in-degree array. For each edge, we add the destination node to the source's adjacency list and increment the destination's in-degree.

💡 This step sets up the graph structure and in-degree counts needed for topological sorting.

Line:

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

💡 The graph and in-degree arrays represent the problem dependencies and readiness for processing.

setup

Initialize queue with zero in-degree nodes

We identify all nodes with zero in-degree and add them to the processing queue. Here, node 0 has zero in-degree and is enqueued.

💡 Nodes with zero in-degree have no dependencies and can start the topological order.

Line:

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

💡 The queue now contains nodes ready to be processed first in topological order.

traverse

Process node 0 from queue

We dequeue node 0 for processing, marking it as processing. Node 0 is added to the topological order list.

💡 Processing nodes in queue builds the topological order step by step.

Line:

node = queue.popleft()
topo_order.append(node)

💡 Node 0 is now being processed and will influence its neighbors.

traverse

Decrease in-degree of node 1 and enqueue if zero

We visit neighbor node 1 of node 0, decrement its in-degree from 1 to 0. Since in-degree is zero, node 1 is enqueued for processing.

💡 Decreasing in-degree tracks dependencies; zero in-degree means ready to process.

Line:

for nei in graph[node]:
    indegree[nei] -= 1
    if indegree[nei] == 0:
        queue.append(nei)

💡 Node 1 is now ready to be processed after node 0.

traverse

Process node 1 from queue

We dequeue node 1 for processing, marking it as processing and adding it to the topological order.

💡 Continuing topological order by processing next ready node.

Line:

node = queue.popleft()
topo_order.append(node)

💡 Node 1 is now being processed and will update its neighbors.

traverse

Decrease in-degree of node 2 and enqueue if zero

We visit neighbor node 2 of node 1, decrement its in-degree from 1 to 0. Node 2 is enqueued since its in-degree is now zero.

💡 This step continues dependency resolution for topological order.

Line:

for nei in graph[node]:
    indegree[nei] -= 1
    if indegree[nei] == 0:
        queue.append(nei)

💡 Node 2 is now ready for processing after node 1.

traverse

Process node 2 from queue

We dequeue node 2 for processing, marking it as processing and adding it to the topological order.

💡 Processing node 2 continues building the topological order.

Line:

node = queue.popleft()
topo_order.append(node)

💡 Node 2 is now being processed and will update its neighbors.

traverse

Decrease in-degree of node 3 and enqueue if zero

We visit neighbor node 3 of node 2, decrement its in-degree from 1 to 0. Node 3 is enqueued since its in-degree is now zero.

💡 Continuing to resolve dependencies for topological order.

Line:

for nei in graph[node]:
    indegree[nei] -= 1
    if indegree[nei] == 0:
        queue.append(nei)

💡 Node 3 is now ready for processing after node 2.

traverse

Process node 3 from queue

We dequeue node 3 for processing, marking it as processing and adding it to the topological order.

💡 Processing node 3 continues the topological order.

Line:

node = queue.popleft()
topo_order.append(node)

💡 Node 3 is now being processed and will update its neighbors.

traverse

Decrease in-degree of node 4 and enqueue if zero

We visit neighbor node 4 of node 3, decrement its in-degree from 1 to 0. Node 4 is enqueued since its in-degree is now zero.

💡 Final dependency resolved for topological order.

Line:

for nei in graph[node]:
    indegree[nei] -= 1
    if indegree[nei] == 0:
        queue.append(nei)

💡 Node 4 is now ready for processing after node 3.

traverse

Process node 4 from queue

We dequeue node 4 for processing, marking it as processing and adding it to the topological order.

💡 Processing last node completes the topological order.

Line:

node = queue.popleft()
topo_order.append(node)

💡 Node 4 is now processed; topological order is complete.

prune

Check for cycle in graph

We verify if the topological order includes all nodes. Since it does, no cycle exists and we proceed.

💡 Detecting cycles is crucial because they invalidate topological sorting.

Line:

if len(topo_order) < n:
    return -1

💡 Graph is a DAG, so longest path computation is valid.

setup

Initialize DP array with 1 for each node

We create a DP array where each node starts with a path length of 1, representing the node itself.

💡 DP array stores longest path lengths ending at each node.

Line:

dp = [1] * n

💡 Each node alone forms a path of length 1.

expand

Update DP for neighbor 1 of node 0

Node 0 has neighbor 1. Since s[1] ('b') != s[0] ('a'), we update dp[1] = max(dp[1], dp[0] + 1) = 2.

💡 DP update extends longest path if adjacent characters differ.

Line:

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

💡 Longest path to node 1 is now length 2.

expand

Update DP for neighbor 2 of node 1

Node 1 has neighbor 2. Since s[2] ('a') != s[1] ('b'), update dp[2] = max(dp[2], dp[1] + 1) = 3.

💡 DP update extends longest path further along the chain.

Line:

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

💡 Longest path to node 2 is now length 3.

expand

Update DP for neighbor 3 of node 2

Node 2 has neighbor 3. Since s[3] ('c') != s[2] ('a'), update dp[3] = max(dp[3], dp[2] + 1) = 4.

💡 DP update continues to extend longest path with different adjacent characters.

Line:

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

💡 Longest path to node 3 is now length 4.

expand

Skip DP update for neighbor 4 of node 3 (characters equal)

Node 3 has neighbor 4. Since s[4] ('a') == s[3] ('c') is false (actually different), update dp[4] = max(dp[4], dp[3] + 1) = 5.

💡 We update DP only if adjacent characters differ to maintain problem constraint.

Line:

if s[nei] != s[node]:
    dp[nei] = max(dp[nei], dp[node] + 1)

💡 Longest path to node 4 is now length 5.

reconstruct

Calculate final answer as max DP value

We find the maximum value in the DP array, which is 5, representing the longest path length with different adjacent characters.

💡 The maximum DP value is the answer to the problem.

Line:

return max(dp)

💡 Longest path length is 5, corresponding to path 0->1->2->3->4.

reconstruct

Return final answer

The algorithm returns 5 as the longest path length with different adjacent characters.

💡 Returning the computed answer completes the algorithm.

Line:

return max(dp)

💡 Final answer is the length of the longest valid path found.

from collections import defaultdict, deque

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

    queue = deque([i for i in range(n) if indegree[i] == 0])  # STEP 2
    topo_order = []
    while queue:  # STEPS 3-11
        node = queue.popleft()  # STEP 3,5,7,9,11
        topo_order.append(node)  # STEP 3,5,7,9,11
        for nei in graph[node]:  # STEPS 4,6,8,10
            indegree[nei] -= 1  # STEPS 4,6,8,10
            if indegree[nei] == 0:  # STEPS 4,6,8,10
                queue.append(nei)  # STEPS 4,6,8,10

    if len(topo_order) < n:  # STEP 12
        return -1

    dp = [1] * n  # STEP 13
    for node in topo_order:  # STEPS 14-17
        for nei in graph[node]:
            if s[nei] != s[node]:
                dp[nei] = max(dp[nei], dp[node] + 1)

    return max(dp)  # STEPS 18-19

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

📊

Longest Path With Different Adjacent Characters - Watch the Algorithm Execute, Step by Step

Watching each step reveals how topological sorting and DP combine to solve a complex graph problem efficiently, making the abstract code concrete and understandable.

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Queue / Stack

0

Visiting: 0

0

1

2

3

4

Visiting: 0

Edge: 0 → 1

0

1

2

3

4

Queue / Stack

1

Visiting: 1

0

1

2

3

4

Visiting: 1

Edge: 1 → 2

0

1

2

3

4

Queue / Stack

2

Visiting: 2

0

1

2

3

4

Visiting: 2

Edge: 2 → 3

0

1

2

3

4

Queue / Stack

3

Visiting: 3

0

1

2

3

4

Visiting: 3

Edge: 3 → 4

0

1

2

3

4

Queue / Stack

4

Visiting: 4

0

1

2

3

4

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Visiting: 0

Edge: 0 → 1

0

1

2

3

4

Visiting: 1

Edge: 1 → 2

0

1

2

3

4

Visiting: 2

Edge: 2 → 3

0

1

2

3

4

Visiting: 3

Edge: 3 → 4

0

1

2

3

4

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Key Takeaways

✓ Topological sorting orders nodes so dependencies are processed before dependents.

This ordering is essential for correctly propagating longest path values without revisiting nodes.

✓ Dynamic programming updates longest path lengths only when adjacent characters differ.

This condition enforces the problem constraint and shows how DP can incorporate problem-specific rules.

✓ Cycle detection via topological sort length check prevents invalid computations.

Without this check, the algorithm could run infinitely or produce incorrect results on cyclic graphs.

Practice

1. Given the following Python code snippet implementing the optimal alien dictionary solution, what is the final returned order for the input words = ["wrt", "wrf", "er", "ett", "rftt"]?

from collections import defaultdict, deque

def alienOrder(words):
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""
        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

    queue = deque([c for c in in_degree if in_degree[c] == 0])
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nei in graph[c]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if len(order) < len(in_degree):
        return ""
    return "".join(order)

print(alienOrder(words))

easy

A. "wretf"

B. "wertf"

C. "wert"

D. "wrtef"

Solution

1. Step 1: Build graph and in-degree map

   Edges: w->e, e->r, r->t, t->f. In-degree counts: w=0, e=1, r=1, t=1, f=1.

2. Step 2: Perform BFS topological sort

   Start with 'w' (in-degree 0), then 'e', 'r', 't', 'f' in order as their in-degree drops to zero.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Order "wertf" respects all precedence edges [OK]

Hint: Trace BFS queue and in-degree updates [OK]

Common Mistakes:

• Stopping early and missing characters
• Misordering characters with same in-degree
• Ignoring prefix invalid case

2. Consider the following buggy implementation of Kahn's Algorithm for course scheduling. Which line contains the subtle bug that can cause incorrect or infinite behavior?

medium

A. Line 6: graph[a].append(b) -- edge direction reversed

B. Line 7: in_degree[a] += 1 -- incorrect in-degree increment

C. Line 10: queue initialization -- wrong nodes enqueued

D. Line 15: in_degree[nei] -= 1 -- decrementing in-degree incorrectly

Solution

1. Step 1: Analyze edge construction

   Prerequisite pairs are (a, b) meaning b -> a edge; reversing to graph[a].append(b) flips direction.

2. Step 2: Consequences of reversed edges

   In-degree counts and BFS queue become invalid, causing wrong order or infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct edge direction is critical for topological sort correctness [OK]

Hint: Check edge direction carefully when building graph [OK]

Common Mistakes:

• Reversing edges when building adjacency list
• Incrementing in-degree on wrong node
• Forgetting to decrement in-degree

3. 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

4. Suppose the problem is modified so that nodes can be revisited multiple times (cycles allowed). Which modification to the iterative DFS approach is necessary to correctly find all paths from source to target without infinite loops?

hard

A. Add a visited set per path to prevent revisiting nodes already in the current path

B. Remove path tracking and rely on global visited set to avoid cycles

C. Use BFS instead of DFS to guarantee shortest paths and avoid cycles

D. No modification needed; the current approach handles cycles correctly

Solution

1. Step 1: Identify cycle problem

   Allowing revisits means cycles can cause infinite loops if not tracked per path.

2. Step 2: Solution approach

   Maintain a visited set per path to avoid revisiting nodes already in the current path, preventing cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Global visited set disallows legitimate different paths; per-path visited set is needed [OK]

Hint: Cycle detection requires per-path visited tracking, not global visited [OK]

Common Mistakes:

• Using global visited set incorrectly
• Assuming no cycles without checks

5. If the problem is extended so that the same element can appear multiple times in the matrix (i.e., reuse allowed), which modification to the topological sort approach is necessary to correctly build the matrix?

hard

A. No change needed; reuse does not affect topological ordering

B. Replace topological sort with a longest path algorithm to handle repeated elements

C. Track counts of each element and assign positions based on frequency, not just order

D. Modify graph to allow self-loops and update cycle detection accordingly

Solution

1. Step 1: Understand reuse impact on matrix construction

   Allowing reuse means elements can appear multiple times, so positions must reflect frequency, not just order.

2. Step 2: Adjust algorithm to track counts and assign positions accordingly

   Topological order alone does not handle multiple occurrences; tracking counts and assigning positions based on frequency is necessary.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency tracking ensures correct placement of repeated elements [OK]

Hint: Reuse implies tracking element counts and positions [OK]

Common Mistakes:

• Assuming reuse needs no algorithm change
• Ignoring frequency of elements
• Replacing topological sort unnecessarily