Longest Palindromic Path in Graph - Video Solutions
3615. Longest Palindromic Path in Graph | Weekly Contest 458 | Leetcode
Longest Palindromic Path in Graph - Video Solution
Watch 4 video solutions for Longest Palindromic Path in Graph, a hard level problem involving String, Dynamic Programming, Bit Manipulation. This walkthrough by Amit Choraria has 630 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: n = 3, edges = [[0,1],[1,2]], label = "aba"
Output: 3
Explanation:
- The longest palindromic path is from node 0 to node 2 via node 1, following the path
0 → 1 → 2forming string"aba". - This is a valid palindrome of length 3.
Example 2:
Input: n = 3, edges = [[0,1],[0,2]], label = "abc"
Output: 1
Explanation:
- No path with more than one node forms a palindrome.
- The best option is any single node, giving a palindrome of length 1.
Example 3:
Input: n = 4, edges = [[0,2],[0,3],[3,1]], label = "bbac"
Output: 3
Explanation:
- The longest palindromic path is from node 0 to node 1, following the path
0 → 3 → 1, forming string"bcb". - This is a valid palindrome of length 3.
Constraints:
1 <= n <= 14n - 1 <= edges.length <= n * (n - 1) / 2edges[i] == [ui, vi]0 <= ui, vi <= n - 1ui != vilabel.length == nlabelconsists of lowercase English letters.- There are no duplicate edges.
Approach Overview
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.
Complexity Analysis
| 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 |