Bird
Raised Fist0

Given n = 3, edges = [[0,1],[1,2]], and s = "aba", what is the final returned value?

easy🧾 Code Trace Q12 of Q15
Topological Sort - Longest Path With Different Adjacent Characters
Consider the following code snippet implementing the optimal solution for the longest path with different adjacent characters problem. Given n = 3, edges = [[0,1],[1,2]], and s = "aba", what is the final returned value?
A-1
B3
C1
D2
Step-by-Step Solution
  1. Step 1: Trace topological order and dp array

    Topological order is [0,1,2]. Initialize dp = [1,1,1]. - For node 0: neighbor 1, s[1] = 'b' != s[0] = 'a', dp[1] = max(1, 1+1) = 2. - For node 1: neighbor 2, s[2] = 'a' != s[1] = 'b', dp[2] = max(1, 2+1) = 3.
  2. Step 2: Compute final answer

    Maximum dp value is 3, which is returned.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    dp array ends as [1, 2, 3], max is 3 [OK]
Quick Trick: Check dp updates along topo order carefully [OK]
Common Mistakes:
MISTAKES
  • Returning dp[node] instead of max(dp)
  • Ignoring character difference condition
  • Miscomputing topological order
Trap Explanation:
PITFALL
  • Some candidates forget to update dp only when characters differ, leading to wrong dp values.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute DP on DAG with character constraints.
Master "Longest Path With Different Adjacent Characters" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes