LeetCode 3615 - Longest Palindromic Path in Graph
We are given an undirected graph with n ≤ 14 vertices. Each vertex has a character label. We may choose any simple path in the graph, meaning a sequence of adjacent vertices in which no vertex is visited more than once.
Difficulty: 🔴 Hard
Topics: String, Dynamic Programming, Bit Manipulation, Graph Theory, Bitmask
Solution
Problem Understanding
We are given an undirected graph with n ≤ 14 vertices. Each vertex has a character label. We may choose any simple path in the graph, meaning a sequence of adjacent vertices in which no vertex is visited more than once.
If the labels encountered along that path form a palindrome, the path is valid. The task is to find the maximum possible number of vertices in such a path.
More formally, if a path visits vertices
$$v_0,v_1,\dots,v_k$$
then the corresponding string is
$$label[v_0],label[v_1],\dots,label[v_k].$$
We seek the maximum value of $k+1$ such that this string is a palindrome.
The constraints are the key observation:
$$n \le 14.$$
This is far too small for polynomial algorithms designed for large graphs, but it is ideal for state compression with bitmasks. A bitmask of length 14 has only
$$2^{14}=16384$$
possible values.
Important edge cases include graphs containing a single node, graphs where no two adjacent vertices share the same label, graphs containing many cycles, and palindromes of both odd and even length. Since vertices may be used at most once, every solution must carefully enforce the simple-path constraint.
Approaches
Brute Force
A direct approach is to enumerate every simple path in the graph.
Starting from every vertex, perform a DFS that explores all simple paths. For each path, construct the corresponding string and test whether it is a palindrome. Record the maximum length encountered.
This approach is correct because every valid simple path is examined. However, the number of simple paths in a graph grows exponentially. In a dense graph with 14 vertices, the number of simple paths is enormous, making exhaustive enumeration impractical.
Key Insight
A palindrome can be built from its center outward.
Suppose we already have a palindromic path whose endpoints are $u$ and $v$. If we can choose unused vertices $u'$ and $v'$ such that
$$label[u'] = label[v'],$$
and
$$u' \text{ is adjacent to } u,$$
and
$$v' \text{ is adjacent to } v,$$
then adding $u'$ and $v'$ to opposite ends produces a larger palindromic path.
Therefore, instead of constructing paths from left to right, we construct them symmetrically from the center.
A state is:
$$(mask,u,v)$$
where:
maskcontains all vertices already used,uandvare the current endpoints,- the vertices in
maskform a palindromic simple path with endpointsuandv.
The graph is small enough that we can explore all reachable states using bitmask dynamic programming.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Exponential, roughly $O(n!)$ in dense graphs | $O(n)$ DFS stack | Enumerates all simple paths |
| Optimal | $O(2^n \cdot n^4)$ worst case | $O(2^n \cdot n^2)$ | Bitmask DP over palindrome states |
Algorithm Walkthrough
- Build the graph adjacency list.
- Create initial palindrome states of length 1. For every vertex
i, the single-character path consisting only ofiis a palindrome. Insert state
$$(1 \ll i,\ i,\ i).$$
3. Create initial palindrome states of length 2. For every edge (u,v), if
$$label[u]=label[v],$$
then the two-vertex path is a palindrome. Insert state
$$((1\ll u)\ |\ (1\ll v),\ u,\ v).$$
4. Maintain a queue containing all discovered states and a set of visited states.
5. Repeatedly remove one state (mask,u,v) from the queue.
6. The number of vertices in the represented path equals
$$\operatorname{popcount}(mask).$$
Update the answer with this value. 7. Attempt to expand the palindrome symmetrically.
For every neighbor nu of u and every neighbor nv of v:
numust not already belong tomask.nvmust not already belong tomask.nu != nv, because the two new endpoints must be distinct unused vertices.label[nu] == label[nv].
- If all conditions hold, create
$$newMask = mask \cup {nu,nv}.$$
The resulting path is still simple and still palindromic. 9. If the new state has not been visited, insert it into the queue. 10. Continue until no new states can be generated. 11. Return the maximum path length found.
Why it works
The invariant is that every stored state represents a valid palindromic simple path whose used vertices are exactly those in mask and whose endpoints are u and v.
The base states are valid palindromes of length 1 and 2. Every transition adds two unused vertices with equal labels to opposite ends of an existing palindrome, preserving both the palindrome property and the simple-path property. Conversely, every palindromic simple path can be reduced by repeatedly removing matching endpoint vertices until reaching either a one-vertex center or a two-vertex center. Therefore every valid palindromic path is reachable from some base state. Since the algorithm explores all reachable states, it finds the maximum possible length.
Python Solution
from typing import List
from collections import deque
class Solution:
def maxLen(self, n: int, edges: List[List[int]], label: str) -> int:
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
queue = deque()
visited = set()
# Odd-length centers.
for i in range(n):
mask = 1 << i
state = (mask, i, i)
visited.add(state)
queue.append(state)
# Even-length centers.
for u, v in edges:
if label[u] == label[v]:
mask = (1 << u) | (1 << v)
state = (mask, u, v)
if state not in visited:
visited.add(state)
queue.append(state)
state = (mask, v, u)
if state not in visited:
visited.add(state)
queue.append(state)
answer = 1
while queue:
mask, u, v = queue.popleft()
answer = max(answer, mask.bit_count())
for nu in graph[u]:
if mask & (1 << nu):
continue
for nv in graph[v]:
if mask & (1 << nv):
continue
if nu == nv:
continue
if label[nu] != label[nv]:
continue
new_mask = mask | (1 << nu) | (1 << nv)
new_state = (new_mask, nu, nv)
if new_state not in visited:
visited.add(new_state)
queue.append(new_state)
return answer
The implementation directly follows the state definition. The graph is stored as an adjacency list. Every single vertex generates an odd-length palindrome center, and every edge whose endpoints share the same label generates an even-length palindrome center.
The queue performs a breadth-first exploration of all palindrome states. For each state, every pair of unused neighboring vertices is examined. Whenever the labels match, the palindrome can be extended by one character on each side. The bitmask guarantees that no vertex is ever reused.
The answer is simply the largest number of set bits observed among all reachable states.
Go Solution
package main
import "math/bits"
func maxLen(n int, edges [][]int, label string) int {
graph := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
type State struct {
mask int
u int
v int
}
queue := make([]State, 0)
visited := make(map[State]bool)
for i := 0; i < n; i++ {
s := State{1 << i, i, i}
visited[s] = true
queue = append(queue, s)
}
for _, e := range edges {
u, v := e[0], e[1]
if label[u] == label[v] {
mask := (1 << u) | (1 << v)
s1 := State{mask, u, v}
if !visited[s1] {
visited[s1] = true
queue = append(queue, s1)
}
s2 := State{mask, v, u}
if !visited[s2] {
visited[s2] = true
queue = append(queue, s2)
}
}
}
answer := 1
head := 0
for head < len(queue) {
cur := queue[head]
head++
if l := bits.OnesCount(uint(cur.mask)); l > answer {
answer = l
}
for _, nu := range graph[cur.u] {
if cur.mask&(1<<nu) != 0 {
continue
}
for _, nv := range graph[cur.v] {
if cur.mask&(1<<nv) != 0 {
continue
}
if nu == nv {
continue
}
if label[nu] != label[nv] {
continue
}
newMask := cur.mask | (1 << nu) | (1 << nv)
next := State{newMask, nu, nv}
if !visited[next] {
visited[next] = true
queue = append(queue, next)
}
}
}
}
return answer
}
The Go implementation mirrors the Python version. A struct is used as the DP state key inside a map. bits.OnesCount computes the number of vertices currently used. The queue is implemented with a slice and a moving head index, avoiding repeated slice reallocations from popping the front.
Worked Examples
Example 1
n = 3
edges = [[0,1],[1,2]]
label = "aba"
Initial states:
| State | Length |
|---|---|
| (001,0,0) | 1 |
| (010,1,1) | 1 |
| (100,2,2) | 1 |
Process (010,1,1):
Neighbors of both endpoints are {0,2}.
Choose:
nu = 0nv = 2
Labels:
label[0] = 'a'
label[2] = 'a'
Match.
New state:
mask = 111
endpoints = (0,2)
Length:
popcount(111) = 3
Answer becomes 3.
Example 2
n = 3
edges = [[0,1],[0,2]]
label = "abc"
Only single-vertex palindrome centers exist.
No edge has equal endpoint labels.
Every expansion attempt fails because no matching labels can be added symmetrically.
Maximum length remains 1.
Example 3
n = 4
edges = [[0,2],[0,3],[3,1]]
label = "bbac"
Initial center:
(1000,3,3)
Neighbors of vertex 3 are {0,1}.
Choose:
nu = 0
nv = 1
Labels:
label[0] = 'b'
label[1] = 'b'
Match.
New state:
mask = 1011
endpoints = (0,1)
Length:
3
Corresponding palindrome:
0 -> 3 -> 1
String:
"bcb"
Answer is 3.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | $O(2^n \cdot n^4)$ | At most $2^n \cdot n^2$ states, each may examine $O(n^2)$ neighbor pairs |
| Space | $O(2^n \cdot n^2)$ | Storage for all reachable states |
The state space contains at most one entry for every combination of bitmask and endpoint pair. Since $n \le 14$, the theoretical maximum is
$$2^{14}\cdot14^2 \approx 3.2\times10^6$$
states, which is manageable for this constraint range.
Test Cases
sol = Solution()
assert sol.maxLen(3, [[0, 1], [1, 2]], "aba") == 3 # example 1
assert sol.maxLen(3, [[0, 1], [0, 2]], "abc") == 1 # example 2
assert sol.maxLen(4, [[0, 2], [0, 3], [3, 1]], "bbac") == 3 # example 3
assert sol.maxLen(1, [], "a") == 1 # single node
assert sol.maxLen(2, [[0, 1]], "aa") == 2 # even palindrome
assert sol.maxLen(2, [[0, 1]], "ab") == 1 # no palindrome edge
assert sol.maxLen(
4,
[[0, 1], [1, 2], [2, 3]],
"abba",
) == 4 # whole path is palindrome
assert sol.maxLen(
4,
[[0, 1], [1, 2], [2, 3]],
"abca",
) == 1 # only single letters
assert sol.maxLen(
5,
[[0, 1], [1, 2], [2, 3], [3, 4]],
"abcba",
) == 5 # odd palindrome
assert sol.maxLen(
5,
[[0, 1], [0, 2], [0, 3], [0, 4]],
"aaaaa",
) == 3 # star graph limits simple path length
Test Summary
| Test | Why |
|---|---|
| Example 1 | Odd-length palindrome |
| Example 2 | No valid extension beyond one vertex |
| Example 3 | Palindrome built around a center |
| Single node | Minimum input size |
| Two equal labels | Smallest even palindrome |
| Two different labels | Length 2 impossible |
"abba" path |
Entire graph forms palindrome |
"abca" path |
Matching endpoints alone are insufficient |
"abcba" path |
Larger odd palindrome |
| Star with all same labels | Graph structure restricts path length |
Edge Cases
Single Vertex Graph
When n = 1, there are no edges. A naive implementation that only starts from edges would incorrectly return 0. The algorithm explicitly inserts every vertex as a length-1 palindrome center, guaranteeing the answer is at least 1.
Even-Length Palindromes
Many palindrome algorithms focus on a single center and naturally handle only odd lengths. Here, palindromes such as "aa" or "abba" require a two-vertex center. The initialization therefore includes every edge whose endpoints have equal labels, ensuring even-length palindromes are explored.
Graphs with Cycles
A graph may contain many cycles. Without careful bookkeeping, a search could revisit vertices and create invalid paths. The bitmask records exactly which vertices have already been used, and every transition requires both new endpoints to be absent from the mask. Consequently every constructed path is simple.
Attempting to Reuse the Same New Vertex on Both Ends
During expansion, two endpoint neighbors might actually be the same vertex. Allowing this would place one vertex at both ends simultaneously and violate the simple-path requirement. The condition nu != nv prevents such invalid constructions.