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.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]], label = "aba"
Output: 3
Explanation:
0 → 1 → 2 forming string "aba".Example 2:
Input: n = 3, edges = [[0,1],[0,2]], label = "abc"
Output: 1
Explanation:
Example 3:
Input: n = 4, edges = [[0,2],[0,3],[3,1]], label = "bbac"
Output: 3
Explanation:
0 → 3 → 1, forming string "bcb".
Constraints:
1 <= n <= 14n - 1 <= edges.length <= n * (n - 1) / 2edges[i] == [ui, vi]0 <= ui, vi <= n - 1ui != vilabel.length == nlabel consists of lowercase English letters.Problem Overview: You are given a graph where each node (or edge) contributes a character. The task is to find the longest path such that the sequence of characters along the path forms a palindrome. The path must respect graph connectivity, and characters from both ends must mirror each other.
Approach 1: Path Enumeration with Palindrome Check (Exponential Time, O(n!))
The most direct idea is to enumerate all possible simple paths in the graph using DFS or backtracking. For each path, build the string formed by node labels and check whether it is a palindrome using two pointers. This requires exploring every permutation-like path combination in dense graphs, leading to factorial growth. Time complexity is roughly O(n! * n) for path exploration and palindrome checks, with O(n) auxiliary space for recursion and path storage. This approach works only for very small graphs and mainly serves as a baseline.
Approach 2: Bitmask Dynamic Programming on Node Pairs (Optimal, O(2^n * n^2))
The key observation is that a palindrome grows symmetrically from both ends. Instead of building paths linearly, track two endpoints (u, v) that represent the current left and right ends of a potential palindromic path. Use a bitmask to record which nodes are already used. A DP state dp[mask][u][v] indicates whether a palindromic path exists that uses nodes in mask with endpoints u and v. Transitions expand the path by choosing neighbors nu of u and nv of v where the characters match. This symmetric expansion ensures the string remains a palindrome while exploring valid graph edges. The DP iterates through masks and endpoint pairs, giving time complexity O(2^n * n^2) and space complexity O(2^n * n^2). This approach combines techniques from graph traversal, dynamic programming, and bitmask state compression.
Recommended for interviews: Start by explaining brute-force path enumeration to show understanding of the search space. Then move to the symmetric DP idea where you grow the palindrome from both ends using a bitmask state. Interviewers usually expect the bitmask DP solution because it demonstrates control over graph states, state compression, and palindrome symmetry.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Path Enumeration | O(n! * n) | O(n) | Very small graphs or conceptual baseline for understanding the problem |
| Bitmask DP on Endpoint Pairs | O(2^n * n^2) | O(2^n * n^2) | General solution when node count is small enough for state compression |
3615. Longest Palindromic Path in Graph | Weekly Contest 458 | Leetcode • Amit Choraria • 550 views views
Watch 3 more video solutions →Practice Longest Palindromic Path in Graph with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor