Practice Longest Palindromic Path in Graph
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Longest Palindromic Path in Graph
Problem Statement
You are given an integer n and an undirected graph with n nodes labeled from 0 to n - 1 and a 2D array edges, where edges[i] = [ui, vi] indicates an edge between nodes ui and vi. You are also given a string label of length n, where label[i] is the character associated with node i. You may start at any node and move to any adjacent node, visiting each node at most once. Return the maximum possible length of a palindrome that can be formed by visiting a set of unique nodes along a valid path.
Source: Longest Palindromic Path in Graph on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
n = 3, edges = [[0,1],[1,2]], label = "aba"
3
# Example 2
n = 3, edges = [[0,1],[0,2]], label = "abc"
1
# Example 3
n = 4, edges = [[0,2],[0,3],[3,1]], label = "bbac"
3
Constraints
How to solve Longest Palindromic Path in Graph
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
With at most 14 nodes, grow a palindrome from its center outward: a state is the visited set plus the two current endpoints, and a step attaches one unvisited neighbor to each end with equal labels. Every palindromic simple path arises this way, so the answer is the largest visited set among reachable states.
Why brute force is not enough
Enumerating all simple paths and testing each as a palindrome is factorial in n; for n = 14 there are about 8.7 times 10^10 orderings, far too many even with pruning.
Approach
- Store adjacency as bitmasks so the unvisited neighbors of a node are one mask operation away.
- Seed with every single node as a center (length 1, both endpoints equal) and with every edge whose endpoints share a label (length 2).
- Process states in order of visited-set size. For endpoints u and v, choose an unvisited neighbor a of u and an unvisited neighbor b of v with a different from b and equal labels; the new state adds both nodes with endpoints a and b.
- The invariant is that each reachable state is a simple path whose visited set is exactly the mask and whose labels read as a palindrome; each step adds a matching pair on the outside, so the property is preserved.
- Return the largest population count over reachable states; it is at least 1.
Walkthrough of Example 3
n = 4, edges = [[0,2],[0,3],[3,1]], label = "bbac" → 3
- n is 4, edges are [[0,2],[0,3],[3,1]], labels are b, b, a, c for nodes 0 through 3.
- Odd seeds give length 1. No edge joins two equal labels (b-a, b-c, c-b), so there are no even seeds and no even-length palindrome is possible.
- From center 3 (label c), pick a = 0 and b = 1: both are unvisited neighbors of 3, distinct, and both labeled b. The new state has visited set {0,1,3}, endpoints 0 and 1, length 3.
- Node 0's remaining neighbor 2 has label a and node 1 has no unvisited neighbor, so no further extension exists; centers 0, 1, and 2 have no equal-label neighbor pairs.
- The maximum is 3, matching the expected output for the path 0, 3, 1 reading bcb.
Time and space
Time O(2^n * n^4) · Space O(2^n * n^2). n is the node count; there are 2^n masks times n^2 endpoint pairs, each trying up to n^2 neighbor pairs, though adjacency masks keep the real work far lower for n = 14; the reachability table is one bit per state.
Interview pitfalls
- Letting both ends extend to the same node, which breaks the simple-path rule and overstates the length.
- Omitting the even-length seeds from adjacent equal-label pairs, which misses every even palindrome.
- Returning 0 when no edge helps; a single node is a palindrome of length 1.
- Treating edges as directed so an extension works from one end but not the other.
- Storing (mask, u, v) and (mask, v, u) separately; normalize u at most v if memory is tight.
Follow-up questions interviewers ask
- How would you reconstruct one longest palindromic path rather than only its length?
- If n grew to about 20, what could you compress or prune to stay within memory?
- What if nodes could be revisited but edges could not; does center-outward growth still work?
Further reading on the technique: Dynamic programming
Related LeetCode Problems
Practice more problems similar to Longest Palindromic Path in Graph.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.